Codeforces Round 425 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

matrices

*2600

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Vasya and Shifts

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputVasya has a set of 4*n* strings of equal length, consisting of lowercase English letters "a", "b", "c", "d" and "e". Moreover, the set is split into *n* groups of 4 equal strings each. Vasya also has one special string *a* of the same length, consisting of letters "a" only.

Vasya wants to obtain from string *a* some fixed string *b*, in order to do this, he can use the strings from his set in any order. When he uses some string *x*, each of the letters in string *a* replaces with the next letter in alphabet as many times as the alphabet position, counting from zero, of the corresponding letter in string *x*. Within this process the next letter in alphabet after "e" is "a".

For example, if some letter in *a* equals "b", and the letter on the same position in *x* equals "c", then the letter in *a* becomes equal "d", because "c" is the second alphabet letter, counting from zero. If some letter in *a* equals "e", and on the same position in *x* is "d", then the letter in *a* becomes "c". For example, if the string *a* equals "abcde", and string *x* equals "baddc", then *a* becomes "bbabb".

A used string disappears, but Vasya can use equal strings several times.

Vasya wants to know for *q* given strings *b*, how many ways there are to obtain from the string *a* string *b* using the given set of 4*n* strings? Two ways are different if the number of strings used from some group of 4 strings is different. Help Vasya compute the answers for these questions modulo 10^{9} + 7.

Input

The first line contains two integers *n* and *m* (1 ≤ *n*, *m* ≤ 500) — the number of groups of four strings in the set, and the length of all strings.

Each of the next *n* lines contains a string *s* of length *m*, consisting of lowercase English letters "a", "b", "c", "d" and "e". This means that there is a group of four strings equal to *s*.

The next line contains single integer *q* (1 ≤ *q* ≤ 300) — the number of strings *b* Vasya is interested in.

Each of the next *q* strings contains a string *b* of length *m*, consisting of lowercase English letters "a", "b", "c", "d" and "e" — a string Vasya is interested in.

Output

For each string Vasya is interested in print the number of ways to obtain it from string *a*, modulo 10^{9} + 7.

Examples

Input

1 1

b

2

a

e

Output

1

1

Input

2 4

aaaa

bbbb

1

cccc

Output

5

Note

In the first example, we have 4 strings "b". Then we have the only way for each string *b*: select 0 strings "b" to get "a" and select 4 strings "b" to get "e", respectively. So, we have 1 way for each request.

In the second example, note that the choice of the string "aaaa" does not change anything, that is we can choose any amount of it (from 0 to 4, it's 5 different ways) and we have to select the line "bbbb" 2 times, since other variants do not fit. We get that we have 5 ways for the request.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/04/2023 17:55:02 (l1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|