← 返回题目列表

AtCoder · icpc2013summer_day2_e

E. 模式语言

中文机器翻译题面 查看原题

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