题目描述

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