题目描述

给出 $n, P$，设

$$f_n = \left(\sum_{p\text{ 是长度为 }n\text{ 的排列}} [\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	无特殊限制