A85968.「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$	无特殊限制