Problem M
Deterministic Finite Automata - Enumeration

You are given a deterministic finite automaton that accepts the language $\mathcal{L}$. You will then be given queries asking for the number of words in $\mathcal{L}$ with a specified length, which you should answer in the order they are given.

Input

The input contains the description of a deterministic finite automaton.

The first line contains four positive integers $n$, $c$, $s$, and $f$, where $n$ is the number of states, $c$ is the size of the alphabet, $s$ is the initial state, and $f$ is the number of final states. The second line consists of a string $\mathrm{\Sigma }={\mathrm{\Sigma }}_1{\mathrm{\Sigma }}_2\dots {\mathrm{\Sigma }}_c$ of $c$ distinct symbols, each of which is a lowercase english character. The third line consists of $f$ distinct positive integers, the set of final states. Then $n$ lines follow, each with $c$ positive integers, describing the symbol table. The $j$-th integer on the $i$-th of those lines represents the state transitioned to from state $i$ upon reading ${\mathrm{\Sigma }}_j$.

Each state is an integer between $1$ and $n$. It is guaranteed that $1\le n\le 2000$, $1\le s\le n$, and $0\le f\le n$.

Finally, the input will contain an integer $m$ and then $m$ lines. The $i$-th line will contain ${\ell }_i$, for $1\le i\le m$, querying for the number of words with length ${\ell }_i$ in $\mathcal{L}$. You may assume that ${\ell }_i\cdot n\le 500000$ for each $i$.

Output

For each of the $m$ queries, output the number of words with the specified length in $\mathcal{L}$. As these numbers can be quite large, output them modulo $1000000007$.

5 2 1 2
ab
4 5
2 3
3 4
4 5
5 4
4 4
5
0
1
2
3
4

0
0
3
8
16

2 4 1 1
acgt
1
2 2 2 2
2 2 2 2
3
0
1
2

1
0
0