CF832E Vasya and Shifts

Vasya 有一个由 $4n$ 个等长字符串组成的集合，这些字符串仅包含小写英文字符 "a"、"b"、"c"、"d" 和 "e"。此外，这个集合被划分为 $n$ 组，每组包含 $4$ 个相同的字符串。Vasya 还有一个特殊字符串 $a$，长度与集合内字符串相同，且只包含字母 "a"。 Vasya 想通过某些操作，将字符串 $a$ 变成一个固定的字符串 $b$，为此他可以以任意顺序使用集合中的字符串。当他使用某个字符串 $x$ 时，$a$ 中每一个字母会根据 $x$ 中对应位置的字母在字母表中的位置（从 $0$ 开始计数）向后移动若干次（“e”后面的字母视为“a”）。 例如，如果 $a$ 中某一位置的字母是 "b"，而 $x$ 中对应位置的字母是 "c"，那么 $a$ 的这个字母会变成 "d"，因为 "c" 是字母表中的第二个字母（从 $0$ 开始计数）。如果 $a$ 的某一位置是 "e"，而 $x$ 的对应位置是 "d"，则该位置会变成 "c"。例如，如果 $a$ 是 "abcde"，$x$ 是 "baddc"，则 $a$ 变成 "bbabb"。 已经使用过的字符串会消失，但由于同组中的四个字符串是相同的，所以可以多次使用（最多 $4$ 次）。 Vasya 现在有 $q$ 个感兴趣的字符串 $b$，他想知道，对每一个 $b$，有多少种方案能从字符串 $a$ 通过上述规则得到字符串 $b$，并且每组 $4$ 个字符串中的用个数不同即视为不同方案。请你帮助 Vasya 计算每个询问的答案，结果对 $10^{9}+7$ 取模。

第一行包含两个整数 $n$ 和 $m$（$1 \leq n,m \leq 500$）——集合中四元组的组数，以及字符串的长度。 接下来 $n$ 行，每行包含一个长度为 $m$ 的字符串 $s$，仅由小写字母 "a"、"b"、"c"、"d" 和 "e" 组成。表示存在 $4$ 个相同的字符串 $s$ 组成一组。 下一行包含一个整数 $q$（$1 \leq q \leq 300$）——Vasya 感兴趣的字符串 $b$ 的个数。 接下来 $q$ 行，每行一个长度为 $m$ 的字符串 $b$，仅由小写字母 "a"、"b"、"c"、"d" 和 "e" 组成。

对于 Vasya 感兴趣的每个字符串，输出一个整数，表示能从字符串 $a$ 变为该字符串的方案数，对 $10^{9}+7$ 取模。

在第一个样例中，集合有 $4$ 个字符串 "b"。对于每个查询字符串 $b$，只有一种方案：选择 $0$ 个 "b" 得到 "a"，选择 $4$ 个 "b" 得到 "e"。因此，对于每个询问，答案都是 $1$。 在第二个样例中，注意选择字符串 "aaaa" 对 $a$ 没有任何影响，因此可以选择 $0$ 到 $4$ 个（共 $5$ 种方法）。而必须选择 "bbbb" 两次，因为其他组合不符合条件。总共有 $5$ 种方案。 由 ChatGPT 5 翻译