Note. We distinguish the order of the children of a node.

"Daiqiang" (a nickname), as the name suggests, likes to strengthen various counting problems, especially those involving polynomials. A "polynomial tree" is a combination of "polynomial" and "tree," which means using polynomials to count trees.

Daiqiang believes that the stability of a rooted tree depends on the number of children each node has. He defines a set of positive integers $D$ and calls a rooted tree "iron" if and only if for every non-leaf node in the tree, if it has $x$ children, then $x \in D$.

For each query $n$, you need to answer how many "iron" rooted trees with $n$ leaves exist, modulo $M$.

Input

The first line contains three positive integers $T, K, M$, representing the number of queries, the range of numbers in the set, and the modulus, respectively.

The next line contains a binary string of length $K-1$. The $x$-th character in the string (starting the count from 2) is '1' if $x \in D$, and '0' otherwise.

Each of the following lines contains a positive integer $n$, representing the number of leaves in the query.

Output

Output $T$ lines, providing the corresponding answers in the order of the queries.

Examples

Input 1

5 2 47
1
1
2
3
4
5

Output 1

1
1
2
5
14

Note 1

These are the Catalan numbers $C_{n-1}$.

Input 2

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

Output 2

1
1
3
11
44
27
31
30
10
26

Subtasks

For $100\%$ of the data, it is guaranteed that $1\le n\le 10^{18}, 2\le K, M\le 50, 1\le T\le 100$.

Special Constraint A: $M$ is a prime number.

Special Constraint B: $\gcd(n, M) = 1$.