P9084 [PA 2018] Skwarki

**This problem is translated from [PA 2018](https://sio2.mimuw.edu.pl/c/pa-2018-1/dashboard/) Round 5 [Skwarki](https://sio2.mimuw.edu.pl/c/pa-2018-1/p/skw/)**. 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$.

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

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

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