M 不同的字母 有 var_1, var_2, … , var_M 。 0, 1, … , 9, var_1, var_2, … , var_M 的 10+M 长度,由 type 的字符组成 N 字符串 给出了 s_1s_2s_3…s_N 。 我想用数字替换该字符串中的每个字母,使其成为回文。 (回文是一串无论从前面还是从后面读都相同的字符串。) 这里,相同的字母必须替换为相同的数字。还给出了所有字母var_i是至少一次的字符串 出现在s_1s_2s_3…s_N中。
字母表 var_i 满足 0 以上 u_i 可以用以下不包含前导零的整数替换。 Mod 计算存在多少种替换方式使得替换后的字符串成为回文。 使用 10^9+7 找到它。 请注意,即使结果字符串相同,如果字母替换不同,它们也会被视为不同。
入力形式
输入按以下格式给出
N M s_1s_2s_3…s_N var_1 u_1 ... var_M u_M
出力形式
更换箱数为 一行输出除以 10^9 + 7 后的余数。
制約
- 1 ≤ N ≤ 500
- 1 ≤ M ≤ 10
- 0 ≤ u_i ≤ 99
- s_i ∈ \{'0', '1', … , '9', var_1, var_2, … , var_M\}
- var_i ∈ \{'a', 'b', … , 'j'\}
- 每个字母 在 var_i 满足 s_1s_2s_3 …s_N 中至少出现一次。
- var_1, var_2, … , var_M 都不同
入出力例
入力例 1
3 1 a1a a 99
出力例 1
19
入力例 2
5 3 jbfjb f 50 b 25 j 5
出力例 2
252
入力例 3
7 3 jag2013 j 53 a 10 g 93
出力例 3
23