Problem Description

This problem is translated from PA 2018 Round 5 Skwarki.

Find how many sequences of length $N$ satisfy the following conditions:

• Each of the $N$ numbers $1$ to $N$ appears exactly once in the sequence.
• Only after performing exactly $K$ operations, the sequence becomes a sequence with only one element.

The operation is defined as follows:

Let $A_i$ be the $i$-th element of the sequence ($1 < i < \mathrm{len}$, where $\mathrm{len}$ is the sequence length). If $A_{i-1} > A_i$ or $A_{i+1} > A_i$, then mark $A_i$. If $A_2 > A_1$, then mark $A_1$. If $A_{\mathrm{len}-1} > A_{\mathrm{len}}$, then mark $A_{\mathrm{len}}$.

Then, delete all marked elements from the sequence.

There may be many valid sequences, so please output the answer modulo $P$.

Input Format

The input contains only one line with three integers $N, K, P$.

Output Format

Output one integer per line, representing the number of valid sequences modulo $P$.

5 3 100000007

4

Hint

Sample 1 Explanation

All valid sequences are listed below:

• $(4,1,3,2,5)$
• $(4,2,3,1,5)$
• $(5,1,3,2,4)$
• $(5,2,3,1,4)$

Constraints

This problem uses bundled testdata.

For $100\%$ of the testdata, it is guaranteed that $1 \le K, N \le 1000$, $N \ge 2$, and $10^8 \le P \le 10^9$.

Translated by ChatGPT 5