Даны $n$ и $P$. Пусть
$$ f_n = \left(\sum_{p\text{ — перестановка длины }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
Примечание
При $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$ |