Uwaga: Rozróżniamy kolejność dzieci węzła.

Dai Qiang, zgodnie ze swoim imieniem, uwielbia wzmacniać (utrudniać) różne zadania zliczające, a w szczególności lubi wielomiany. Tak zwane „wielodrzewa” to połączenie „wielomianów” i „drzew”, co oznacza użycie wielomianów do zliczania drzew.

Dai Qiang uważa, że stabilność drzewa ukorzenionego zależy od liczby dzieci każdego węzła w tym drzewie. Dlatego zdefiniował zbiór dodatnich liczb całkowitych $D$ i nazwał drzewo ukorzenione „żelaznym” wtedy i tylko wtedy, gdy dla każdego węzła wewnętrznego (niebędącego liściem) tego drzewa, jeśli ma on $x$ dzieci, to $x \in D$.

Dai Qiang zadaje Ci $T$ zapytań, każde z liczbą $n$. Dla każdego zapytania odpowiedz, ile istnieje „żelaznych” drzew ukorzenionych o $n$ liściach. Odpowiedź podaj modulo $M$.

Wejście

W pierwszej linii znajdują się trzy dodatnie liczby całkowite $T, K, M$, oznaczające liczbę zapytań, zakres liczb w zbiorze oraz moduł.

W kolejnej linii znajduje się ciąg 01 o długości $K-1$. Jeśli $x$-ty znak w ciągu (licząc od 2) jest równy 1, oznacza to, że $x \in D$, w przeciwnym razie $x \notin D$.

W każdej z kolejnych linii znajduje się jedna dodatnia liczba całkowita $n$, oznaczająca liczbę liści w zapytaniu.

Wyjście

Wypisz $T$ linii, zawierających odpowiedzi na zapytania w kolejności ich występowania.

Przykład

Przykład 1 Wejście

5 2 47
1
1
2
3
4
5

Przykład 1 Wyjście

1
1
2
5
14

Uwagi

Są to liczby Catalana $C_{n-1}$.

Przykład 2 Wejście

10 15 50
11101010101101
1
2
3
4
5
10
100
10000
998244353
1145141919810

Przykład 2 Wyjście

1
1
3
11
44
27
31
30
10
26

Podzadania

Dla $100\%$ danych wejściowych zachodzi $1\le n\le 10^{18}, 2\le K, M\le 50, 1\le T\le 100$.

Specjalne ograniczenie A: $M$ jest liczbą pierwszą.

Specjalne ograniczenie B: $\gcd(n,M)=1$.