1534번 - 다각형 자르기

문제

세준이는 N개의 점을 가진 볼록 다각형을 가지고 있다. 다각형을 한 번 자를 때, 반드시 점에서 점으로 자르는 것만 가능하고, 또, 하나의 다각형이 반드시 두 개로 나누어 져야 한다. 그리고, 모든 점은 구분된다고 한다.

예를 들어, 정사각형을 자르는 데는 3가지 방법이 존재한다. 두 가지는 대각선으로 자르는 방법이고, 한 가지는 자르지 않는 방법이다.

볼록 N각형을 K개의 다각형으로 자르는 경우의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. N은 3보다 크거나 같고, 100보다 작거나 같다. K는 1보다 크거나 같고, 100보다 작거나 같다.

출력

첫째 줄에 정답을 1000000000으로 나눈 나머지를 출력한다. 만약 N각형을 K개의 다각형으로 자르는 것이 불가능할 경우에는 -1을 출력한다.

제한

힌트