A5943. 「2020-2021 集训队作业」Permutation

给出 $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$。

一行一个整数表示答案。

对于 $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$ | $=998244353$ |
| $6$ | $3 \times 10^4$ | $=998244353$ |
| $7$ | $10^5$ | $=998244353$ |
| $8$ | $3 \times 10^5$ | $=998244353$ |
| $9$ | $5 \times 10^5$ | $=998244353$ |
| $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$ | 无特殊限制 |