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