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