Problem8595--DPL_5_G : Balls and Boxes 7

8595: DPL_5_G : Balls and Boxes 7

[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 can contain an arbitrary number of balls (including zero).

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.

Sample 1 Input 

3 5

Sample 1 Output 

5

Sample 2 Input 

5 3

Sample 2 Output 

41

Sample 3 Input 

100 100

Sample 3 Output 

193120002

HINT

相同题目：DPL_5_G。

Source/Category

 
Submit