CF832E.Vasya and Shifts

Vasya 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 109 + 7.

瓦西娅有一组 $4n$ 个等长的字符串，每个字符串仅由小写英文字母 “a”、“b”、“c”、“d” 和 “e” 组成。此外，该集合被划分为 $n$ 组，每组恰好包含 4 个完全相同的字符串。瓦西娅还拥有一个特殊字符串 $a$，其长度与上述字符串相同，且仅由字母 “a” 构成。

瓦西娅希望从字符串 $a$ 出发，得到某个给定的目标字符串 $b$。为此，他可以以任意顺序使用自己集合中的字符串。当他使用某个字符串 $x$ 时，字符串 $a$ 中的每个字符将根据字符串 $x$ 中对应位置字符在字母表中的序号（从零开始计数）进行若干次“向后移动一位”的操作：即每次将当前字母替换为字母表中其后继字母（“a”→“b”，“b”→“c”，“c”→“d”，“d”→“e”，“e”→“a”）。具体而言，若 $x$ 中某位置的字符是第 $k$ 个字母（从零开始计数，即 “a” 对应 $0$，“b” 对应 $1$，……，“e” 对应 $4$），则 $a$ 中对应位置的字符将向后循环移动 $k$ 次。

例如，若 $a$ 中某字符为 “b”，而 $x$ 中对应位置字符为 “c”，则因 “c” 是从零开始计数的第 $2$ 个字母，故该 “b” 将向后移动 $2$ 次变为 “d”。又如，若 $a$ 中某字符为 “e”，而 $x$ 中对应位置字符为 “d”，则因 “d” 是第 $3$ 个字母，故该 “e” 向后移动 $3$ 次变为 “c”（e → a → b → c）。再举一例：若 $a = \texttt{abcde}$，$x = \texttt{baddc}$，则 $a$ 变为 $\texttt{bbabb}$。

每次使用的字符串随即消失，但瓦西娅可多次使用相同内容的字符串（即来自不同组的相同字符串，或同一组中多个副本，因每组有 4 个相等字符串，故最多可用 4 次）。

现瓦西娅有 $q$ 个待查询的目标字符串 $b$，他想知道：对每个 $b$，有多少种方式能从初始字符串 $a$ 出发，利用给定的 $4n$ 个字符串，最终恰好得到 $b$？若两种方案中至少存在某一组（共 $n$ 组）所使用的字符串数量不同，则视为不同方案。请帮助瓦西娅计算所有查询的答案，结果对 $10^9 + 7$ 取模。

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.

第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 500$）—— 分别表示字符串集合中四元组的个数，以及所有字符串的长度。

接下来的 $n$ 行中，每行包含一个长度为 $m$ 的字符串 $s$，由小写英文字母 "a"、"b"、"c"、"d" 和 "e" 组成。这表示存在一个由四个相同字符串 $s$ 构成的四元组。

下一行包含一个整数 $q$（$1 \leq q \leq 300$）—— 表示 Vasya 感兴趣的字符串 $b$ 的个数。

接下来的 $q$ 行中，每行包含一个长度为 $m$ 的字符串 $b$，由小写英文字母 "a"、"b"、"c"、"d" 和 "e" 组成 —— 即 Vasya 感兴趣的字符串。

For each string Vasya is interested in print the number of ways to obtain it from string a, modulo 109 + 7.

对于每个字符串，瓦西娅感兴趣的是：计算从字符串 a 得到它的方案数（对 $10^9 + 7$ 取模）。

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.

在第一个例子中，我们有 4 个字符串 "b"。对于每个字符串 b，我们只有一种选择方式：选择 0 个字符串 "b" 得到 "a"，选择 4 个字符串 "b" 得到 "e"。因此，每个查询有 1 种方式。

在第二个例子中，注意字符串 "aaaa" 的选择不会产生任何影响，即我们可以任意选择其数量（从 0 到 4，共 5 种不同方式），而字符串 "bbbb" 必须恰好选择 2 次，因为其他选择方式均不满足条件。因此，该查询共有 5 种方式。