Given $n$ and $P$, let
$$ f_n = \left(\sum_{p\text{ is a permutation of length }n} [\exists i \in [1,n] , p_i = i][\exists i \in [1,n] , p_i = n - i + 1]\right) \bmod\ P $$
You need to find the value of $\bigoplus_{i=1}^n f_i$.
Input
A single line containing two integers $n$ and $P$.
Output
A single line containing an integer representing the answer.
Examples
Input 1
2 100000
Output 1
1
Note 1
For $n=1$, the permutation $(1)$ satisfies both conditions, so $f_1 = 1$.
For $n=2$, the permutations $(1,2)$ and $(2,1)$ each fail to satisfy one of the conditions, so $f_2 = 0$.
Therefore, the answer is $1\oplus 0 = 1$.
Subtasks
For $100\%$ of the data, $1 \leq n \leq 10^7$ and $n + 1 \leq P \leq 10^9$.
| Test Case ID | $n \leq$ | $P$ |
|---|---|---|
| $1$ | $18$ | No special restrictions |
| $2$ | $60$ | |
| $3$ | $300$ | |
| $4$ | $1000$ | $=998244353$ |
| $5$ | $5000$ | |
| $6$ | $3 \times 10^4$ | |
| $7$ | $10^5$ | |
| $8$ | $3 \times 10^5$ | |
| $9$ | $5 \times 10^5$ | |
| $10$ | $1000$ | Is a prime number |
| $11$ | $10^4$ | |
| $12$ | $10^5$ | |
| $13$ | $10^6$ | |
| $14$ | $10^7$ | |
| $15$ | $5000$ | No special restrictions |
| $16$ | $3 \times 10^4$ | |
| $17$ | $10^5$ | |
| $18$ | $5 \times 10^5$ | |
| $19$ | $2 \times 10^6$ | |
| $20$ | $10^7$ |