합분해 2

면접 대비

시간 제한1초메모리 제한512 MB

요약

0 이상 N 이하의 정수 K개를 더해 합이 N이 되는 순서 있는 방법의 수를 1,000,000,000으로 나눈 나머지를 구합니다.

문제

0부터 $N$ 까지의 정수 $K$ 개를 더해서 그 합이 $N$ 이 되는 경우의 수를 구하는 프로그램을 작성하시오.

더하는 순서가 다르면 다른 경우로 센다. 예를 들어 $1+2$ 와 $2+1$ 은 서로 다른 경우이다. 같은 수를 여러 번 써도 된다.

첫째 줄에 두 정수 $N$ 과 $K$ 가 주어진다. ( $1 \le N \le 5{,}000$ , $1 \le K \le 5{,}000$ )

첫째 줄에 경우의 수를 $1{,}000{,}000{,}000$ 으로 나눈 나머지를 출력한다.