給定 $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$。
輸出格式
一行一個整數表示答案。
範例
範例輸入 1
2 100000
範例輸出 1
1
說明 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 | 無特殊限制 |
| 16 | $3 \times 10^4$ | |
| 17 | $10^5$ | |
| 18 | $5 \times 10^5$ | |
| 19 | $2 \times 10^6$ | |
| 20 | $10^7$ |