Sum Decomposition 2

Write a program that counts the ways to add $K$ integers, each between $0$ and $N$ inclusive, so that their sum is $N$.

Order matters: $1+2$ and $2+1$ count as different ways. The same number may be used more than once.

The first line contains two integers $N$ and $K$ ($1 \le N \le 5{,}000$, $1 \le K \le 5{,}000$).

Print the number of ways modulo $1{,}000{,}000{,}000$ on the first line.