합 분해
면접 대비시간 제한2초메모리 제한128 MB
0부터 N까지의 정수 K개를 순서 있게 골라 합이 N이 되는 경우의 수를 1,000,000,000으로 나눈 나머지로 구합니다.
문제
0부터 N까지의 정수 중 K개를 순서 있게 골라 합이 N이 되게 하는 경우의 수를 구한다.
선택한 수들의 순서가 다르면 다른 경우로 센다. 예를 들어 1+2와 2+1은 서로 다른 경우이다. 같은 수를 여러 번 사용할 수 있다.
입력
첫째 줄에 두 정수 N과 K가 주어진다. (1 <= N <= 200, 1 <= K <= 200)
출력
경우의 수를 1,000,000,000으로 나눈 나머지를 출력한다.