You have ~n~ identical stickers to hand out to ~k~ distinct people. Each person may receive any number of stickers, including zero. Stickers are indistinguishable, so two distributions that give every person the same count are the same.

Count the number of ways to give out all ~n~ stickers. Since the answer can be large, output it modulo ~10^9 + 7~.

Input

A single line containing two integers ~n~ and ~k~.

Output

Print one integer: the number of ways to distribute the stickers, modulo ~10^9 + 7~.

Constraints

• ~0 \le n \le 10^6~
• ~1 \le k \le 10^6~

Example 1

Input

3 2

Output

4

Explanation

The four distributions ~(person 1, person 2)~ are ~(0, 3)~, ~(1, 2)~, ~(2, 1)~, and ~(3, 0)~.

Example 2

Input

0 3

Output

1

Explanation

There are no stickers, so everyone gets zero. That is one valid distribution.

Example 3

Input

2 3

Output

6

Explanation

The non-negative integer solutions of ~x_1 + x_2 + x_3 = 2~ are ~(2, 0, 0)~, ~(0, 2, 0)~, ~(0, 0, 2)~, ~(1, 1, 0)~, ~(1, 0, 1)~, and ~(0, 1, 1)~.