Problem B
Cricket Deadpool
Kyle is working on a graduate degree in biology, and as part of his research he is studying the eating habits of a certain snake species. One of these snakes, named Donna, lives in a terrarium in Kyle’s lab, where she is fed a steady diet of crickets. To pass the time (and to procrastinate writing their theses), Kyle and his labmates have set up a betting game that involves predicting the order in which Donna will eat the crickets. (Such a betting game is called a deadpool.)
There are initially $n$ crickets in Donna’s terrarium, labelled $1, 2, \ldots , n$ (Kyle spent an entire afternoon painting tiny numbers on the crickets’ backs). The deadpool participants want to know in how many different orders Donna could eat all the crickets. If Donna only ever ate one cricket at a time, it’s easy to see that there are $n!$ $(n$ factorial) orders, but sometimes Donna eats more than one cricket in a single bite. For example, if $n = 5,$ and if Donna can eat up to two crickets at a time, then Donna could eat cricket $\# 4$ in her first bite, crickets $\# 2$ and $\# 5$ in her second bite, cricket $\# 3$ in her third bite, and cricket $\# 1$ in her fourth bite. This might be represented as:
\[ \{ 4\} \ \ \{ 2,5\} \ \ \{ 3\} \ \ \{ 1\} \]Note that since the order of crickets in any multi-cricket bite doesn’t matter, this is the same as:
\[ \{ 4\} \ \ \{ 5,2\} \ \ \{ 3\} \ \ \{ 1\} \]Given $n$ and the maximum number of crickets Donna can eat in a single bite, help the deadpool participants by determining the number of orders in which Donna can eat all the crickets.
Input
Input consists of a single line containing two space-separated integers, $n$ and $k,$ the number of crickets initially in the terrarium $(1 \leq n \leq 100)$ and the maximum number of crickets Donna can eat in a single bite $(1 \leq k \leq 10),$ respectively.
Output
Output a single integer: the number of orders in which Donna can eat all $n$ crickets. Since the answer might be large, report it modulo the prime number $10^9 + 7.$
| Sample Input 1 | Sample Output 1 |
|---|---|
4 1 |
24 |
| Sample Input 2 | Sample Output 2 |
|---|---|
4 2 |
66 |
