Description

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

Input Format

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

Output Format

Output a single integer on one line, the answer.

3 10

5

Hint

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