問題 E : Pattern Language

問題文

m 個の相異なるアルファベット var_0,  var_1,   … ,  var_{m-1} がある． 0,   1,   … ,   9,   var_0,   var_1,   … ,   var_{m-1} の 10+m 種類の文字からなる，長さ N の文字列 s_0s_1s_2…s_{N-1} が与えられる． この文字列における各アルファベットを数字で置き換えて回文になるようにしたい．(回文とは，前から読んでも後ろから読んでも同じ文字列をあらわす．) ここで，同じアルファベットは同じ数字で置き換えなければならない．また与えられたすべてのアルファベットvar_iは少なくとも，一度は文字列s_0s_1s_2…s_{N-1}にあらわれる．

アルファベット var_i は 0 以上 u_i 以下の，leading zero を含まない整数に置き換える事ができる． 置き換えた後の文字列が回文になるような置き換え方が何通り存在するかを，mod 10^9+7 で求めよ． なお，アルファベットの置き換え方が異なれば，得られる文字列が同じでも異なるものとして数える．

入力形式

入力は以下の形式で与えられる

N m
s_0s_1s_2…s_{N-1}
var_0 u_0
...
var_{m-1} u_{m-1}

出力形式

置き換え方の場合の数を 10^9 + 7 で割った剰余を一行で出力せよ．

制約

• 1 ≤ N ≤ 500
• 1 ≤ m ≤ 10
• 0 ≤ u_i ≤ 99
• s_i ∈ \{'0',   '1',   … ,   '9',   var_0,   var_1,   … ,   var_{m-1}\}
• var_i ∈ \{'a',   'b',   … ,   'j'\}
• 各アルファベット var_i は s_0s_1s_2 …s_{N-1} に少なくとも一度は現れる．
• var_0,  var_1,  … ,  var_{m-1} はすべて異なる

入出力例

入力例 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