다각형 나누기
시간 제한2초메모리 제한128 MB
변이 N개인 convex 다각형을 서로 교차하지 않는 대각선으로 잘라 정확히 K개의 다각형으로 나누는 방법의 수를 1000000000으로 나눈 나머지로 구하고, 불가능하면 -1을 출력합니다.
문제
세준이는 서로 구분되는 N개의 꼭짓점을 가진 볼록 다각형을 가지고 있다. 한 번 자를 때는 현재 있는 다각형의 두 꼭짓점을 잇는 선분만 사용할 수 있으며, 그 선분은 하나의 다각형을 정확히 두 개의 다각형으로 나누어야 한다.
볼록 N각형을 정확히 K개의 다각형으로 나누는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 두 정수 N과 K가 주어진다.
3 <= N <= 1001 <= K <= 100
출력
가능한 나누기 방법의 수를 1000000000으로 나눈 나머지를 출력한다.
N각형을 정확히 K개의 다각형으로 나누는 것이 불가능하면 -1을 출력한다.