Problem8597--DPL_5_I : Balls and Boxes 9

8597: DPL_5_I : Balls and Boxes 9

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

SubmitSolved: 1Submit Num: 1StatisticsShowOff!

Description

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 distinguished from the other.
  • Each box is not distinguished from the other.
  • Each ball can go into only one box and no one remains outside of the boxes.
  • Each box must contain at least one ball.

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

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

Input

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 \leq n \leq 1,000$
$1 \leq k \leq 1,000$

Sample 1 Input 

4 3

Sample 1 Output 

6

Sample 2 Input 

10 5

Sample 2 Output 

42525

Sample 3 Input 

100 30

Sample 3 Output 

203169470

HINT

相同题目：DPL_5_I。

Source/Category

 
Submit