Taxiarchos228, CC BY-SA 3.0, via Wikimedia Commons.
You are taking a group of schoolchildren to see the eclipse!
There are $n$ children in
the class, and each bus holds $k$ children. In fact, each bus must
contain exactly $k$ children, since based on your long
experience with children on buses, you know that if there are
extra empty seats, children will start moving around the bus
between seats and chaos will ensue. Hence, you must divide the
$n$ children into groups
of exactly $k$, with none
left over. As you have the children start counting off, you
wonder: how many different ways would there be to do this?
Input
The input consists of two integers on a single line:
$n$ ($0 \leq n \leq 10^6$), the number of
children on the trip, and $k$ ($1
\leq k \leq n$), the number of children that should be
in each group.
Output
Output a single line containing the number of distinct
configurations of the $n$
children into groups of size $k$. Two configurations are considered
distinct if and only if there are at least two children who are
in the same group in one configuration, but different groups in
the other configuration. Since the number of configurations
could be quite large, output it modulo $10^9 + 7$.
| Sample Input 1 |
Sample Output 1 |
4 2
|
3
|
| Sample Input 2 |
Sample Output 2 |
7 7
|
1
|
| Sample Input 3 |
Sample Output 3 |
5 3
|
0
|
| Sample Input 4 |
Sample Output 4 |
22 2
|
749310484
|
