$M$ 個的不同字母 $var_1,  var_2,   … ,  var_M$ 给定。给出由 $0,   1,   … ,   9,   var_1,   var_2,   … ,   var_M$ 这 $10+M$ 种字符组成的长度为 $N$ 的字符串 $s_1s_2s_3…s_N$。希望将该字符串中的每个字母用数字替换，使其成为回文串（即无论从前往后读还是从后往前读都表示相同的字符串）。在这里，相同的字母必须用相同的数字代替。另外，给定的所有字母 $var_i$ 必须至少出现一次在字符串 $s_1s_2s_3…s_N$ 中。

可以将字母 $var_i$ 替换为不包含前导零的介于 $0$ 和 $u_i$ 之间的整数。求出满足替换后的字符串是回文串的不同替换方法的数量，取模 $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