Примечание. Мы различаем порядок детей узла.

Daiqiang, оправдывая свое имя, любит усложнять различные задачи на подсчет, особенно те, что связаны с многочленами. Так называемое «многодерево» — это комбинация «многочлена» и «дерева», то есть использование многочленов для подсчета деревьев.

Daiqiang считает, что степень стабильности корневого дерева зависит от количества детей у каждого узла дерева. Он задает множество положительных целых чисел $D$ и называет корневое дерево «железным» тогда и только тогда, когда для каждого нелистового узла этого дерева, имеющего $x$ детей, выполняется условие $x \in D$.

Daiqiang каждый раз спрашивает вас, сколько существует «железных» корневых деревьев с $n$ листьями. Ответ выведите по модулю $M$.

Входные данные

В первой строке заданы три положительных целых числа $T, K, M$, обозначающие количество запросов, диапазон чисел в множестве и модуль соответственно.

В следующей строке задана строка из 01 длиной $K-1$. Если $x$-й символ строки (считая с 2) равен 1, то $x \in D$, иначе $x \notin D$.

Далее следует $T$ строк, каждая из которых содержит одно положительное целое число $n$, обозначающее количество листьев в запросе.

Выходные данные

Выведите $T$ строк, содержащих ответы на запросы в порядке их поступления.

Примеры

Пример 1

Входные данные

5 2 47
1
1
2
3
4
5

Выходные данные

1
1
2
5
14

Примечание

Это числа Каталана $C_{n-1}$.

Пример 2

Входные данные

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

Выходные данные

1
1
3
11
44
27
31
30
10
26

Подзадачи

Для $100\%$ данных гарантируется $1\le n\le 10^{18}, 2\le K, M\le 50, 1\le T\le 100$.

Специальное ограничение A: $M$ — простое число.

Специальное ограничение B: $\gcd(n,M)=1$.