How do you add?

Source: UVa

Version: Phuoc Hung OJ Extended

Problem Statement

Given $N$ and $K$, count ordered $K$-tuples of nonnegative integers whose sum is exactly $N$. Different orders count separately. Print the result modulo $1{,}000{,}000$.

Input

The only line contains $N,K$.

Output

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

Subtasks

• Subtask 1 — 20 points: N <= 20; K <= 8.
• Subtask 2 — 30 points: N <= 60; K <= 60.
• Subtask 3 — 50 points: 1 <= N <= 100; 1 <= K <= 100.

Examples

Input

20 2

Output

21

Explanation

For $N=20,K=2$, the first value can be any integer from 0 to 20 and the second is then fixed, giving 21 ways.