Balls and Boxes 4

Balls	Boxes	Any way	At most one ball	At least one ball
Distinguishable	Distinguishable	1	2	3
Indistinguishable	Distinguishable	4	5	6
Distinguishable	Indistinguishable	7	8	9
Indistinguishable	Indistinguishable	10	11	12

Problem

You have $n$ balls and $k$ boxes. You want to put these balls into the boxes.

Find the number of ways to put the balls under the following conditions:

• Each ball is not distinguished from the other.
• Each box is distinguished from the other.
• Each ball can go into only one box and no one remains outside of the boxes.
• Each box can contain an arbitrary number of balls (including zero).

Note that you must print this count modulo $10^9+7$.

Input

$n$ $k$

The first line will contain two integers $n$ and $k$.

Output

Print the number of ways modulo $10^9+7$ in a line.

Constraints

• $1 \le n \le 1000$
• $1 \le k \le 1000$

Sample Input 1

5 3

Sample Output 1

21

Sample Input 2

10 5

Sample Output 2

1001

Sample Input 3

100 100

Sample Output 3

703668401

---