Подсказка
Изначально для этой задачи планировалась предыстория, соответствующая названию, но из-за того, что автор оказался слишком ленив, она так и не была написана до начала соревнования. Надеемся, что в будущем она появится в Lightnovel OJ.
Мы называем $k$-перестановкой такую перестановку $p$, что для всех $1 \le i < n$ выполняется условие $|p_i - p_{i+1}| \neq k$.
Вам даны натуральные числа $n$ и $M$. Далее следует $q$ запросов, в каждом из которых дано число $k$. Для каждого запроса определите, сколько существует $k$-перестановок порядка $n$. Поскольку ответ может быть очень большим, выведите его по модулю $M$.
Входные данные
В первой строке содержатся три натуральных числа $n, q, M$, обозначающие порядок перестановки, количество запросов и модуль соответственно.
Далее следуют $q$ строк, в каждой из которых содержится натуральное число $k$, обозначающее запрос на количество $k$-перестановок.
Выходные данные
Выведите $q$ строк, в каждой из которых содержится одно целое число — количество перестановок по модулю $M$.
Примеры
Пример 1
5 5 998244353 1 2 3 4 5
14 28 48 72 120
Пример 2
3 1 1000000007 1
0
Пример 3
4 1 1000000007 2
10
Подзадачи
| Подзадача | Баллы | Ограничения | $M$ — простое |
|---|---|---|---|
| 1 | 10 | $n \le 9, k \le n, q = n$ | Да |
| 2 | 14 | $n \le 16, k \le n, q = n$ | Да |
| 3 | 15 | $n \le 200, k = 1, q = 1$ | Да |
| 4 | 16 | $n \le 200, k = n, q = 1$ | Да |
| 5 | 8 | $n \le 10^3, k = 1, q = 1$ | Да |
| 6 | 9 | $n \le 10^3, k = 2, q = 1$ | Да |
| 7 | 16 | $n \le 10^3, k \le n, q = n$ | Да |
| 8 | 11 | $n \le 2\,000, k \le n, q = n$ | Нет |
| 9 | 1 | $n \le 2\,000, k \le n, q = n$ | Да |
Для 100% данных гарантируется $1 \le k \le n \le 2\,000$, $10^8 \le M \le 10^9$, все значения $k$ в запросах различны. Для 99% данных гарантируется $n \le 10^3$.