Vasya有一组4n个等长的字符串,由小写英文字母“a”、“b”、“c”、“d”和“e”组成。此外,该集合被分成 n 组,每组 4 个相等的字符串。 Vasya 还有一个长度相同的特殊字符串 a,仅由字母“a”组成。
Vasya 想要从字符串 a 中获取某个固定的字符串 b,为了做到这一点,他可以按任意顺序使用他的集合中的字符串。当他使用某个字符串 x 时,字符串 a 中的每个字母都会被字母表中的下一个字母替换,次数与字符串 x 中相应字母的字母表位置(从零开始计数)相同。在此过程中,字母表中“e”之后的下一个字母是“a”。
例如,如果a中的某个字母等于“b”,并且x中相同位置的字母等于“c”,则a中的字母等于“d”,因为“c”是从零开始计数的第二个字母。如果a中的某个字母等于“e”,并且x中相同位置上的字母是“d”,则a中的字母变为“c”。例如,如果字符串 a 等于“abcde”,字符串 x 等于“baddc”,则 a 变为“bbabb”。
使用过的字符串会消失,但 Vasya 可以多次使用相同的字符串。
Vasya 想知道对于 q 个给定的字符串 b,使用给定的 4n 个字符串集从字符串中获取字符串 b 有多少种方法?如果某组 4 个字符串中使用的字符串数量不同,则两种方法会有所不同。帮助 Vasya 计算这些问题对 109 + 7 求模的答案。
输入
第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 500) - 集合中四个字符串的组数,以及所有字符串的长度。
接下来的n行每一行包含一个长度为m的字符串s,由小写英文字母“a”、“b”、“c”、“d”和“e”组成。这意味着有一组四个字符串等于 s。
下一行包含单个整数 q (1 ≤ q ≤ 300) — Vasya 感兴趣的字符串 b 的数量。
接下来的 q 个字符串都包含一个长度为 m 的字符串 b,由小写英文字母“a”、“b”、“c”、“d”和“e”组成——这是 Vasya 感兴趣的字符串。
输出
对于每个字符串,Vasya 感兴趣的是打印从字符串 a 中获取该字符串的方法数量,模 109 + 7。
示例
输入 #1
1 1 b 2 a e
输出 #1
1 1
输入 #2
2 4 aaaa bbbb 1 cccc
输出 #2
5
注意
在第一个示例中,我们有 4 个字符串“b”。那么对于每个字符串b我们有唯一的方法:分别选择0个字符串“b”得到“a”和选择4个字符串“b”得到“e”。因此,我们对每个请求有 1 种方式。
在第二个示例中,请注意,字符串“aaaa”的选择不会改变任何内容,也就是说,我们可以选择任意数量的字符串(从0到4,有5种不同的方式),并且我们必须选择“bbbb”行两次,因为其他变体不适合。我们发现我们有 5 种请求方式。