AT_joisc2011_deciphering 解読 (Deciphering)
题目描述
### 题目大意
给定 $L$ 长字符串，求出其所有不同非空子串（即原字符串或原字符串删除其中若干字符得到的字符串）且同时符合 $M$ 条规则的不同字符串个数，每一条规则如下：
- 字符 $b_i$ 不紧接与字符 $a_i$ 之后。
输入格式
第一行，一个整数 $L$。
第二行，一个字符串。
第三行，一个整数 $M$。
后面 $M$ 行，每行两个整数 $a_i,b_i$，空格隔开。
输出格式
一行一个整数表示答案对 $10^7$ 取余后的结果。
### 输入输出样例
输入样例 #1：
```
5
JOIOI
1
I O
```
输出样例 #1：
```
15
```
符合要求的字符串有 `I`, `II`, `J`, `JI`, `JII`, `JO`, `JOI`, `JOII`, `JOO`, `JOOI`, `O`, `OI`, `OII`, `OO`, `OOI` 这 $15$ 个。
输入样例 #2：
```
26
ABCDEFGHIJKLMNOPQRSTUVWXYZ
0
```
输出样例 #2：
```
7108863
```
### 时空限制
时间限制：500 ms；空间限制：64 MB。
说明/提示
$1\le L\le 3\times10^5,0\le M\le26\times26$。