Uwagi
Pierwotnie miała istnieć historia w tle pasująca do tytułu, ale ze względu na to, że autor był zbyt leniwy, nie napisał ani słowa przed rozpoczęciem zawodów. Miejmy nadzieję, że w przyszłości pojawi się ona w Lightnovel OJ.
Treść zadania
Nazywamy $k$-permutacją taką permutację $p$, że dla każdego $1 \le i < n$ zachodzi $|p_i - p_{i+1}| \neq k$.
Dane są liczby całkowite dodatnie $n$ oraz $M$. Następnie otrzymasz $q$ zapytań, każde zawierające liczbę $k$. Dla każdego zapytania odpowiedz, ile permutacji stopnia $n$ jest $k$-permutacjami. Ponieważ wynik może być bardzo duży, wyprowadź go modulo $M$.
Wejście
Pierwsza linia zawiera trzy liczby całkowite dodatnie $n, q, M$, oznaczające odpowiednio stopień permutacji, liczbę zapytań oraz moduł.
Następnie $q$ linii, z których każda zawiera liczbę całkowitą dodatnią $k$, oznaczającą zapytanie o liczbę $k$-permutacji.
Wyjście
Wyprowadź $q$ linii, z których każda zawiera jedną liczbę całkowitą będącą wynikiem modulo $M$.
Przykład
Wejście 1
5 5 998244353 1 2 3 4 5
Wyjście 1
14 28 48 72 120
Wejście 2
3 1 1000000007 1
Wyjście 2
2
Wejście 3
4 1 1000000007 1
Wyjście 3
10
Podzadania
Dla 100% danych wejściowych zachodzi $1 \le k \le n \le 2\,000$, $10^8 \le M \le 10^9$, a wartości $k$ w zapytaniach są parami różne. Dla 99% danych wejściowych zachodzi $n \le 10^3$.
| Numer podzadania | Punkty | $n$ | $k$ | $q$ | $M$ jest liczbą pierwszą |
|---|---|---|---|---|---|
| 1 | 10 | $\le 9$ | $= n$ | Tak | |
| 2 | 14 | $\le 16$ | |||
| 3 | 15 | $\le 200$ | $= 1$ | $= 1$ | Tak |
| 4 | 16 | $= n$ | $= n$ | ||
| 5 | 8 | $\le 10^3$ | $= 1$ | $= 1$ | Tak |
| 6 | 9 | $= 2$ | |||
| 7 | 16 | $= n$ | Nie | ||
| 8 | 11 | ||||
| 9 | 1 | $\le 2\,000$ |