$n$ と $P$ が与えられる。$f_n$ を次のように定義する。
$$ 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$ の値を求めよ。
入力
一行に2つの整数 $n, P$ が与えられる。
出力
答えを一行に出力せよ。
入出力例
入力 1
2 100000
出力 1
1
注記
$n=1$ のとき、順列 $(1)$ は上記の2つの条件を両方満たすため、$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$ |