Pattern Language

Time limit5sMemory limit512 MB

Summary

Each of M letters takes a digit up to its own limit u_i; count assignments that make the whole string a palindrome, where positions paired by mirror symmetry must get equal digits.

Level: Medium6 of 10
Topics: Union-find, Math, Combinatorics, Implementation
Solved: No attempts yet

Problem

There are $M$ distinct letters $var_1, var_2, \ldots, var_M$ . You are given a string $s_1s_2s_3\ldots s_N$ of length $N$ consisting of the $10+M$ characters $0, 1, \ldots, 9, var_1, var_2, \ldots, var_M$ . You want to replace each letter in this string with a digit so that the result is a palindrome. (A palindrome reads the same forwards and backwards.) Equal letters must be replaced by equal digits. Every given letter $var_i$ appears at least once in $s_1s_2s_3\ldots s_N$ .

Letter $var_i$ can be replaced by an integer between $0$ and $u_i$ inclusive, without leading zeros. Count the number of replacement choices that make the resulting string a palindrome, modulo $10^9+7$ . Two choices are considered different if they assign different digits to any letter, even if the resulting string is the same.

Input

The input is given in the following format.

$N$ $M$

$s_1s_2s_3\ldots s_N$

$var_1$ $u_1$

$...$

$var_M$ $u_M$

Output

Print the number of replacement choices modulo $10^9 + 7$ on one line.

Constraints

$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'\}$
Each letter $var_i$ appears at least once in $s_1s_2s_3 \ldots s_N$ .
$var_1, var_2, \ldots, var_M$ are all distinct.

Examples3

Example 1
Input
```
3 1
a1a
a 99
```
Expected output
```
19
```
Example 2
Input
```
5 3
jbfjb
f 50
b 25
j 5
```
Expected output
```
252
```
Example 3
Input
```
7 3
jag2013
j 53
a 10
g 93
```
Expected output
```
23
```