C :: Counting the ways

Time Limit: 2 Seconds    Memory Limit: 65536 KB

Any ACMer likes to solve puzzles just like you. Now we have a puzzle here. Solve it if you can!

This puzzle is a new version of word search puzzle. We have a table of English lowercase letters with R rows and C columns. There are N strings of English lowercase letters that should be built from the table.

To build a string S from the table, starting from an arbitrary cell of the table, each time you move to an adjacent cell (i.e. up, down, left or right) given that you do not leave the table. As you move, you write down letters of the cells you pass, on a piece of paper. At the end, if the string on the paper equals to S, we say S is built from the table. Note that you might pass the same cell multiple times.

One  way  of  building  a  string  from  the  table  can  be  represented  as  a  sequence  of  ordered  pairs,  each denoting one cell of the table in order you passed them. Two ways are different if their representative sequences are different. You have to find for each  test, the different  number  of ways to build if from table. 

 

Input

In the first line there is T (T ≤ 50), the number of tests that follow. Each test begins with two integers R and C (1 ≤ R, C ≤ 50). Next R lines each contain C English lowercase letters. j‐th letter of i‐th line is the letter in row i and column j of the table. After that, there will be an integer N (1 ≤ N ≤ 50) which is the number of strings. Each of the next N lines contains a string of length at most 50. Each string consists of only English lowercase letters. 

 

Output

For each string in each test, print the number of ways that we can build it from the table in a single line.  As this number can be very large, you should print it modulo 1,000,000,007. 

 

Sample Input

1
3 4
acmp
umic
tpmp
3
aut
acmicpc
pmp

Sample Output

1
4
6

Submit

Source: AUT 2012