A sequence of length $2n$ is called interesting if and only if it satisfies the following three conditions:

1. It is a permutation $\{a_i\}$ of the $2n$ integers from $1$ to $2n$;
2. All odd-indexed terms satisfy $a_1 < a_3 < \cdots < a_{2n-1}$, and all even-indexed terms satisfy $a_2 < a_4 < \cdots < a_{2n}$;
3. Any two adjacent terms $a_{2i-1}$ and $a_{2i}$ ($1 \le i \le n$) satisfy the condition that the odd-indexed term is less than the even-indexed term, i.e., $a_{2i-1} < a_{2i}$.

The task is: for a given $n$, find the number of different interesting sequences of length $2n$. Since the final answer may be very large, you are only required to output the answer modulo $P$.

Input

The input contains two space-separated integers $n$ and $P$. The input data guarantees: 50% of the data satisfies $n \le 1000$, and 100% of the data satisfies $n \le 1000000$ and $P \le 1000000000$.

Output

Output a single integer representing the number of different interesting sequences of length $2n$ modulo $P$.

Examples

Input 1

3 10

Output 1

5

Note

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)$, and $(1,4,2,5,3,6)$.