Vasya and Shifts

题意翻译

有 $n$ 组，每组含有 $4$ 个完全相同的字符串，所有的 $4n$ 个字符串长度相同，且每个字符串均由小写字母 `a`,`b`,`c`,`d`,`e` 组成。另外，还有一个特殊的字符串 $a$ 全由字母 `a` 组成，字符串 $a$ 的长度与这 $4n$ 个字符串的长度相同，均为输入中给定的数字 $m$ 。 为了把字符串 $a$ 变成一些固定的字符串 $b$ ，可以按照任何顺序使用给出的这些字符串。当使用字符串 $x$ 时， $a$ 中的每个字母都会变成对应的下一个字母，并重复若干次，重复次数与 $x$ 中对应位置字母在字母表中的位置相同（从零开始）。特别地，在 `e` 后的下一个字母是 `a` 。 例如， $a$ 中的某个字母 `b` 和 $x$ 中的 `c` 位置相同，则 $a$ 中的字母变为 `d`，因为 `c` 是第二个字母表字母，`b`替换两次就变为 `d` 。如果 $a$ 中的某个字母 `e` 和 $x$ 中的 `d` 位置相同，则 $a$ 中的字母变为 `c` ，即 `e` 变换三次后的结果。例如，如果字符串 $a$ 等于 `abcde` ，而字符串 $x$ 等于 `baddc` ，则 $a$ 变为 `bbabb` 。**可以把这个操作看成两个五进制数字进行不进位的加法运算。** 被使用过的字符串将会消失，但可以多次使用相等的字符串。 现在给出 $q$ 个询问 $b$ ，要求对每个询问求出，使用给定的 $4n$ 个字符串，有多少种不同的方法可以让 $a$ 变成 $b$ 。两个方案不同，当且仅当存在某一组字符串，其在两种方案中被使用的字符串的个数不同。输出答案对 $10^9+7$ 取模后的结果。 `by DeaphetS,Modification cfkk`

题目描述

Vasya has a set of $ 4n $ 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 $ 4n $ 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 $ .

输入输出格式

输入格式

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.

输出格式

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

输入输出样例

输入样例 #1

1 1
b
2
a
e

输出样例 #1

1
1

输入样例 #2

2 4
aaaa
bbbb
1
cccc

输出样例 #2

5

说明

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.