DPL_5_C : Balls and Boxes 3 - Problem - MYOJ

Problem8591--DPL_5_C : Balls and Boxes 3

8591: DPL_5_C : Balls and Boxes 3

_{[Creator : ]}

Time Limit : 1.000 sec Memory Limit : 256 MiB

Submit Solved: 1 Submit Num: 1 Statistics ShowOff!

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

Sample 1 Input

4 3

Sample 1 Output

Sample 2 Input

10 3

Sample 2 Output

Sample 3 Input

100 100

Sample 3 Output

437918130

HINT

相同题目：DPL_5_C。

Source/Category

Submit