합 분해

0부터 N까지의 정수 중 K개를 순서 있게 골라 합이 N이 되게 하는 경우의 수를 구한다.

선택한 수들의 순서가 다르면 다른 경우로 센다. 예를 들어 1+2와 2+1은 서로 다른 경우이다. 같은 수를 여러 번 사용할 수 있다.

첫째 줄에 두 정수 N과 K가 주어진다. (1 <= N <= 200, 1 <= K <= 200)

경우의 수를 1,000,000,000으로 나눈 나머지를 출력한다.