Dane są $n$ oraz $P$. Niech
$$ f_n = \left(\sum_{p\text{ jest permutacją długości }n} [\exists i \in [1,n] , p_i = i][\exists i \in [1,n] , p_i = n - i + 1]\right) \bmod\ P $$
Musisz obliczyć wartość $\bigoplus_{i=1}^n f_i$.
Wejście
Wiersz zawierający dwie liczby całkowite $n$ oraz $P$.
Wyjście
Wiersz zawierający jedną liczbę całkowitą będącą wynikiem.
Podzadania
Dla $100\%$ danych wejściowych: $1 \leq n \leq 10^7 , n + 1 \leq P \leq 10^9$.
| Numer testu | $n \leq$ | $P$ |
|---|---|---|
| 1 | 18 | brak specjalnych ograniczeń |
| 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 | jest liczbą pierwszą |
| 11 | $10^4$ | |
| 12 | $10^5$ | |
| 13 | $10^6$ | |
| 14 | $10^7$ | |
| 15 | 5000 | brak specjalnych ograniczeń |
| 16 | $3 \times 10^4$ | |
| 17 | $10^5$ | |
| 18 | $5 \times 10^5$ | |
| 19 | $2 \times 10^6$ | |
| 20 | $10^7$ |
Przykład
Wejście 1
2 100000
Wyjście 1
1
Uwagi
Dla $n=1$ permutacja $(1)$ spełnia oba powyższe warunki, zatem $f_1 = 1$;
Dla $n=2$ permutacje $(1,2)$ oraz $(2,1)$ nie spełniają co najmniej jednego z warunków, zatem $f_2 = 0$;
Stąd odpowiedź wynosi $1\oplus 0 = 1$.