Given four stacks $a, s_1, s_2, b$. Initially, stack $a$ contains $n$ elements, which are $1, 2, \dots, n$ from bottom to top, while $s_1, s_2, b$ are all empty.

You can perform the following operations any number of times:

1. If $a$ is not empty, move the top element of $a$ to the top of $s_1$.
2. If $s_1$ is not empty, move the top element of $s_1$ to the top of $s_2$.
3. If $s_2$ is not empty, move the top element of $s_2$ to the top of $b$.

However, you have an additional requirement: at any time, the values in $s_2$ from top to bottom must be strictly decreasing.

Finally, all elements are in $b$. Write them down as a sequence from top to bottom.

Heterogeneous Sequence Property Problem: Find the number of permutations that cannot be obtained, modulo a prime $M$.

Input

Each test case contains multiple sets of test data.

The first line of the input contains two integers $N, M$.

Output

For each set of test data, output a single integer representing the answer.

Examples

Input 1

4 998244353
5 1000000007
6 1000000009

Output 1

2
30
326

Subtasks

For $50\%$ of the data, $N \leq 5\,000$.

For $100\%$ of the data, $1 \leq N \leq 5 \times 10^5$.

Note

1. The number of test cases was not provided during the contest; "participants should evaluate this themselves."
2. The range of the modulus $M$ was not provided during the contest; "participants should evaluate this themselves."
3. The memory limit was not provided during the contest; it is set to 1 GB on QOJ.