题目描述

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

数据范围与提示

对于 $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$