Problem D
Drowning Combinatorist
loglogloglog. Brandon Greg Jr. is sometimes a drowning combinatorist.
A permutation of length $n$ can be represented as some order of the integers $\{ 1,2,\ldots ,n\} $. A run of length $k$ in a permutation is $k$ consecutive elements that appear in increasing or decreasing order. For example, $[5,2,4,3,1]$ is a permutation of length $5$, where (among other runs), $[2,4]$ is a run of length $2$ and $[4,3,1]$ is a run of length $3$.
Brandon found a way to count the number of permutations of length $n$ that have runs of length at most $k$. He wants you to do the same so he could check his answers. Since the numbers get very large, Brandon will ask for it modulo some prime $p$ of his choice.
Input
The only line of input contains three space-separated integers $n, k, p$ ($1\le n\le 2\, 000$, $2\le k\le 7$, $10^8<p\le 10^9+9$), where $n$ is the length of the permutations, $k$ is the maximum length of a run, and $p$ is the prime of Brandon’s choice.
Output
Output one integer representing the number of permutations of length $n$ that have runs of length at most $k$, modulo $p$.
| Sample Input 1 | Sample Output 1 |
|---|---|
1 7 1000000007 |
1 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 2 1000000007 |
4 |
| Sample Input 3 | Sample Output 3 |
|---|---|
9 3 1000000009 |
224458 |
