22439번 - Pattern Language 다국어

$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$ はすべて異なる