P3200 [HNOI2009] Interesting Sequence

We call a sequence of length $2n$ interesting if and only if it satisfies the following three conditions: - It is a permutation of the $2n$ integers from $1$ to $2n$, written as $a_1, a_2, \dots, a_{2n}$. - All odd-indexed terms satisfy $a_1 < a_3 < \dots < a_{2n-1}$, and all even-indexed terms satisfy $a_2 < a_4 < \dots < a_{2n}$. - For every adjacent pair $a_{2i-1}$ and $a_{2i}$, it holds that $a_{2i-1} < a_{2i}$. For a given $n$, find the number of different interesting sequences of length $2n$. Since the answer can be large, output the answer modulo $p$.

One line with two positive integers $n, p$.

Output a single integer on one line, the answer.

Constraints For $50\%$ of the testdata, $1 \le n \le 1000$. For $100\%$ of the testdata, $1 \le n \le 10^6$, $1 \le p \le 10^9$. Sample explanation The $5$ interesting sequences are (1, 2, 3, 4, 5, 6), (1, 2, 3, 5, 4, 6), (1, 3, 2, 4, 5, 6), (1, 3, 2, 5, 4, 6), (1, 4, 2, 5, 3, 6). Translated by ChatGPT 5