给出 $n,P$，设
$$ 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 $$
你需要求出 $\bigoplus_{i=1}^n f_i$ 的值。
输入格式
输入一行两个整数 $n,P$。
输出格式
一行一个整数表示答案。
样例数据
样例输入
2 100000
样例输出
1
样例解释
$n=1$ 时排列 $(1)$ 满足上述两个条件，故 $f_1 = 1$；
$n=2$ 时排列 $(1,2),(2,1)$ 均有一个条件不满足，故 $f_2 = 0$；
所以答案为 $1\oplus 0 = 1$。
子任务
对于 $100\%$ 的数据，$1 \leq n \leq 10^7 , n + 1 \leq P \leq 10^9$。
| 测试点编号 | $n \leq$ | $P$ |
|---|---|---|
| $1$ | $18$ | 无特殊限制 |
| $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$ | 是质数 |
| $11$ | $10^4$ | |
| $12$ | $10^5$ | |
| $13$ | $10^6$ | |
| $14$ | $10^7$ | |
| $15$ | $5000$ | 无特殊限制 |
| $16$ | $3 \times 10^4$ | |
| $17$ | $10^5$ | |
| $18$ | $5 \times 10^5$ | |
| $19$ | $2 \times 10^6$ | |
| $20$ | $10^7$ |