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 2000$, $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$.

-----Examples-----
Sample Input 1:
1 7 1000000007
Sample Output 1:
1

Sample Input 2:
3 2 1000000007
Sample Output 2:
4

Source: kattis | Difficulty: HARD


Solutions: