8589: DPL_5_A : Balls and Boxes 1
[Creator : ]
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:
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 can contain an arbitrary number of balls (including zero).
| 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$
$1 \leq k \leq 1,000$
Sample 1 Input
2 3
Sample 1 Output
9
Sample 2 Input
10 5
Sample 2 Output
9765625
Sample 3 Input
100 100
Sample 3 Output
424090053
HINT
相同题目：DPL_5_A。