E - Pattern Language Editorial /

Time Limit: 5 sec / Memory Limit: 128 MB

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 以下の，leading zero を含まない整数に置き換える事ができる． 置き換えた後の文字列が回文になるような置き換え方が何通り存在するかを，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