{"problem":{"name":"E. Vasya and Shifts","description":{"content":"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","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF832E"},"statements":[{"statement_type":"Markdown","content":"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.\n\nVasya 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_\".\n\nFor 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_\".\n\nA used string disappears, but Vasya can use equal strings several times.\n\nVasya 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.\n\n## Input\n\nThe 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.\n\nEach 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_.\n\nThe next line contains single integer _q_ (1 ≤ _q_ ≤ 300) — the number of strings _b_ Vasya is interested in.\n\nEach 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\n## Output\n\nFor each string Vasya is interested in print the number of ways to obtain it from string _a_, modulo 109 + 7.\n\n[samples]\n\n## Note\n\nIn 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.\n\nIn 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.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Vasya 有一组由 $4n$ 个等长字符串组成的集合，这些字符串由小写英文字母 \"_a_\"、\"_b_\"、\"_c_\"、\"_d_\" 和 \"_e_\" 组成。此外，该集合被划分为 $n$ 组，每组包含 $4$ 个完全相同的字符串。Vasya 还有一个特殊的字符串 $a$，其长度相同，且全部由字母 \"_a_\" 组成。\n\nVasya 希望通过使用他集合中的字符串，将字符串 $a$ 变为某个固定的字符串 $b$。他可以按任意顺序使用集合中的字符串。当他使用某个字符串 $x$ 时，字符串 $a$ 中的每个字母都会根据字符串 $x$ 中对应位置字母在字母表中的序号（从零开始计数）向后移动相应次数。在这个过程中，字母 \"_e_\" 的下一个字母是 \"_a_\"。\n\n例如，如果 $a$ 中某个字母是 \"_b_\"，而 $x$ 中对应位置的字母是 \"_c_\"，那么 $a$ 中的该字母会变为 \"_d_\"，因为 \"_c_\" 是字母表中从零开始的第二个字母。如果 $a$ 中某个字母是 \"_e_\"，而 $x$ 中对应位置的字母是 \"_d_\"，那么 $a$ 中的该字母会变为 \"_c_\"。例如，如果字符串 $a$ 是 \"_abcde_\"，字符串 $x$ 是 \"_baddc_\"，那么 $a$ 会变为 \"_bbabb_\"。\n\n使用过的字符串会消失，但 Vasya 可以多次使用相同的字符串。\n\nVasya 想知道，对于给定的 $q$ 个字符串 $b$，有多少种方式可以使用给定的 $4n$ 个字符串将字符串 $a$ 变为 $b$？两种方式不同，当且仅当从某组 $4$ 个字符串中使用的数量不同。请帮助 Vasya 计算这些询问的答案，结果对 $10^9 + 7$ 取模。\n\n第一行包含两个整数 $n$ 和 $m$（$1 \\leq n, m \\leq 500$）——集合中四字符串组的数量，以及所有字符串的长度。\n\n接下来的 $n$ 行，每行包含一个长度为 $m$ 的字符串 $s$，由小写英文字母 \"_a_\"、\"_b_\"、\"_c_\"、\"_d_\" 和 \"_e_\" 组成。这表示存在一组四个等于 $s$ 的字符串。\n\n下一行包含一个整数 $q$（$1 \\leq q \\leq 300$）——Vasya 感兴趣的字符串 $b$ 的数量。\n\n接下来的 $q$ 行，每行包含一个长度为 $m$ 的字符串 $b$，由小写英文字母 \"_a_\"、\"_b_\"、\"_c_\"、\"_d_\" 和 \"_e_\" 组成——Vasya 感兴趣的字符串。\n\n对于每个 Vasya 感兴趣的字符串，请输出将字符串 $a$ 变为该字符串的方式数，结果对 $10^9 + 7$ 取模。\n\n在第一个例子中，我们有 $4$ 个字符串 \"_b_\"。对于每个字符串 $b$，我们只有一种方式：选择 $0$ 个 \"_b_\" 得到 \"_a_\"，选择 $4$ 个 \"_b_\" 得到 \"_e_\"。因此，每个询问都有 $1$ 种方式。\n\n在第二个例子中，注意选择字符串 \"_aaaa_\" 不会改变任何内容，即我们可以选择任意数量的它（从 $0$ 到 $4$，共 $5$ 种不同方式），并且我们必须选择字符串 \"_bbbb_\" 恰好 $2$ 次，因为其他选择都不符合要求。因此，我们得到该询问有 $5$ 种方式。\n\n## Input\n\n第一行包含两个整数 $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 感兴趣的字符串。\n\n## Output\n\n对于每个 Vasya 感兴趣的字符串，请输出将字符串 $a$ 变为该字符串的方式数，结果对 $10^9 + 7$ 取模。\n\n[samples]\n\n## Note\n\n在第一个例子中，我们有 $4$ 个字符串 \"_b_\"。对于每个字符串 $b$，我们只有一种方式：选择 $0$ 个 \"_b_\" 得到 \"_a_\"，选择 $4$ 个 \"_b_\" 得到 \"_e_\"。因此，每个询问都有 $1$ 种方式。在第二个例子中，注意选择字符串 \"_aaaa_\" 不会改变任何内容，即我们可以选择任意数量的它（从 $0$ 到 $4$，共 $5$ 种不同方式），并且我们必须选择字符串 \"_bbbb_\" 恰好 $2$ 次，因为其他选择都不符合要求。我们得到该询问有 $5$ 种方式。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $, with $ 1 \\leq n, m \\leq 500 $.  \nLet $ \\Sigma = \\{a, b, c, d, e\\} $, identified with $ \\mathbb{Z}_5 = \\{0, 1, 2, 3, 4\\} $ via $ a \\mapsto 0, b \\mapsto 1, c \\mapsto 2, d \\mapsto 3, e \\mapsto 4 $.  \n\nLet $ A = (0, 0, \\dots, 0) \\in \\mathbb{Z}_5^m $ be the initial string (all 'a').  \nLet $ S = \\{s_1, s_2, \\dots, s_n\\} \\subseteq \\mathbb{Z}_5^m $ be the set of $ n $ distinct string templates, each representing a group of 4 identical strings.  \nFor each $ s_k \\in S $, define its *effect vector* $ v_k \\in \\mathbb{Z}_5^m $ by $ v_k[i] = \\text{value of } s_k[i] \\in \\mathbb{Z}_5 $.  \n\nLet $ q \\in \\mathbb{Z}^+ $, $ 1 \\leq q \\leq 300 $, be the number of target strings.  \nFor each query $ j \\in \\{1, \\dots, q\\} $, let $ b_j \\in \\mathbb{Z}_5^m $ be the target string, and define the *required shift vector* $ d_j = (d_{j,1}, \\dots, d_{j,m}) \\in \\mathbb{Z}_5^m $ by $ d_j = b_j - A = b_j \\pmod{5} $.  \n\n**Constraints**  \n1. For each group $ k \\in \\{1, \\dots, n\\} $, we may choose any number $ x_k \\in \\{0, 1, 2, 3, 4\\} $ of strings from its group of 4.  \n2. The total effect of the chosen strings must satisfy:  \n   $$\n   \\sum_{k=1}^n x_k \\cdot v_k \\equiv d_j \\pmod{5}, \\quad \\text{for each query } j.\n   $$\n\n**Objective**  \nFor each query $ j \\in \\{1, \\dots, q\\} $, compute the number of integer solutions $ (x_1, \\dots, x_n) \\in \\{0,1,2,3,4\\}^n $ to the system:  \n$$\n\\sum_{k=1}^n x_k v_k \\equiv d_j \\pmod{5}\n$$  \nOutput the result modulo $ 10^9 + 7 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF832E","tags":["matrices"],"sample_group":[["1 1\nb\n2\na\ne","1\n1"],["2 4\naaaa\nbbbb\n1\ncccc","5"]],"created_at":"2026-03-03 11:00:39"}}