Pattern Language

$M$개의 서로 다른 알파벳 $var_1, var_2, \ldots, var_M$이 있다. $0, 1, \ldots, 9, var_1, var_2, \ldots, var_M$의 $10+M$ 종류 문자로 이루어진 길이 $N$의 문자열 $s_1s_2s_3\ldots s_N$이 주어진다. 이 문자열의 각 알파벳을 숫자로 바꾸어 회문이 되게 하려 한다. (회문이란 앞에서 읽어도 뒤에서 읽어도 같은 문자열을 말한다.) 같은 알파벳은 같은 숫자로 바꾸어야 한다. 또한 주어진 모든 알파벳 $var_i$는 문자열 $s_1s_2s_3\ldots s_N$에 적어도 한 번은 나타난다.

알파벳 $var_i$는 $0$ 이상 $u_i$ 이하의, leading zero를 포함하지 않는 정수로 바꿀 수 있다. 바꾼 뒤의 문자열이 회문이 되는 교체 방법이 몇 가지인지 mod $10^9+7$로 구하여라. 알파벳의 교체 방법이 다르면 얻어지는 문자열이 같아도 다른 것으로 센다.

입력은 다음 형식으로 주어진다.

$N$ $M$

$s_1s_2s_3\ldots 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', \ldots, '9', var_1, var_2, \ldots, var_M\}$
• $var_i ∈ \{'a', 'b', \ldots, 'j'\}$
• 각 알파벳 $var_i$는 $s_1s_2s_3 \ldots s_N$에 적어도 한 번은 나타난다.
• $var_1, var_2, \ldots, var_M$은 모두 서로 다르다