Problem8598--DPL_5_J : Balls and Boxes 10

8598: DPL_5_J : Balls and Boxes 10

[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 not 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.

Constraints

$1 \leq n \leq 1,000$
$1 \leq k \leq 1,000$

Sample 1 Input 

5 3

Sample 1 Output 

5

Sample 2 Input 

10 5

Sample 2 Output 

30

Sample 3 Input 

100 100

Sample 3 Output 

190569292

HINT

相同题目：DPL_5_J。

Source/Category

 
Submit