Sum Decomposition

Interview

Time limit2sMemory limit128 MB

Summary

Count ordered sequences of K integers from 0 to N whose sum equals N, modulo 1,000,000,000.

Level: Easy3 of 10
Topics: Dynamic programming, Combinatorics, Math
Solved: No attempts yet

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.

Examples2

Example 1
Input
```
20 2
```
Expected output
```
21
```
Example 2
Input
```
6 4
```
Expected output
```
84
```