Sum Decomposition

Time limit

Memory limit

128 MB

Problem

Choose K integers from 0 through N, in order, so that their sum is N. Count how many such ordered choices are possible.

If the order of the chosen numbers differs, the choices are counted separately. For example, 1+2 and 2+1 are different. The same number may be used more than once.

Input

The first line contains two integers N and K. (1 <= N <= 200, 1 <= K <= 200)

Output

Print the number of possible choices modulo 1,000,000,000.