8596: DPL_5_H : Balls and Boxes 8
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 at most 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
Output
Constraints
$1 \leq k \leq 1,000$
Sample 1 Input
5 10
Sample 1 Output
1
Sample 2 Input
200 100
Sample 2 Output
0