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 で割った剰余を一行で出力せよ.
3 1 a1a a 99
19
5 3 jbfjb f 50 b 25 j 5
252
7 3 jag2013 j 53 a 10 g 93
23