Deciphering(解読) - joi2011-day3
時間制限: 0.5秒
メモリ制限: 64MB
あなたは A から Z の文字で書かれた IOI 国の機密文書を手に入れた．この機密文書の原文は IOI 語で書かれている．機密文書からいくつかの文字（0 文字でもよい）を消すことで原文が得られる．
IOI 語の文章は 1 文字以上からなる文字列であり，相異なる M 個の次のような規則を満たす：
- 規則 i (1 \leq i \leq M)：文字 A_i の直後に文字 B_i は来ない．
与えられた機密文書の原文として考えられるものの個数を 10\,000\,000 で割った余りを求めよ．ただし，消し方が異なっても同じ原文であれば 1 つと数える．
課題
機密文書から考えられる原文の個数を 10\,000\,000 で割った余りを求めよ．
制限
| 1 \leq L \leq 300\,000 | 機密文書の長さ |
| 0 \leq M \leq 26 \times 26 | IOI 語の規則の個数 |
入力
標準入力から以下の入力を読み込め．
- 1 行目には整数 L が書かれており，機密文書の長さが L であることを表す．
- 2 行目には機密文書が書かれている．これは長さ L の A から Z までの文字からなる文字列である．
- 3 行目には整数 M が書かれており，IOI 語の規則の個数が M であることを表す．
- 続く M 行には IOI 語の規則の情報が書かれている．i + 3 行目 (1 \leq i \leq M) には，規則 i を表す A から Z までの文字 A_i, B_i が空白を区切りとして書かれている．A_i = A_j かつ B_i = B_j なる規則 j (j \neq i) は存在しない．
出力
標準出力に考えられる原文の個数を 10\,000\,000 で割った余りを 1 行で出力せよ．
採点基準
- 採点用データのうち，配点の 10% 分については，L \leq 15 を満たす．
- 採点用データのうち，配点の 40% 分については，L \leq 5\,000 を満たす．
入出力の例
| 入力例 1 | 出力例 1 |
|---|---|
| 5 JOIOI 1 I O |
15 |
この入力例では，\rm{I}, \rm{II}, \rm{J}, \rm{JI}, \rm{JII}, \rm{JO}, \rm{JOI}, \rm{JOII}, \rm{JOO}, \rm{JOOI}, \rm{O}, \rm{OI}, \rm{OII}, \rm{OO}, \rm{OOI} が考えられる原文である．
| 入力例 2 | 出力例 2 |
|---|---|
| 26 ABCDEFGHIJKLMNOPQRSTUVWXYZ 0 |
7108863 |