Hide

# Problem DDrowning 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

Hide

Please log in to submit a solution to this problem