解読 (Deciphering)

あなたは A から Z の文字で書かれた IOI 国の機密文書を手に入れた．この機密文書の原文は IOI 語で書かれている．機密文書からいくつかの文字（0 文字でもよい）を消すことで原文が得られる．

IOI 語の文章は 1 文字以上からなる文字列であり，相異なる M 個の次のような規則を満たす：

規則 i (1 ≤ i ≤ M)：文字 Ai の直後に文字 Bi は来ない．

与えられた機密文書の原文として考えられるものの個数を 10 000 000 で割った余りを求めよ．ただし，消し方が異なっても同じ原文であれば 1 つと数える．

機密文書から考えられる原文の個数を 10 000 000 で割った余りを求めよ．

標準入力から以下の入力を読み込め．

1 行目には整数 L が書かれており，機密文書の長さが L であることを表す．
2 行目には機密文書が書かれている．これは長さ L の A から Z までの文字からなる文字列である．
3 行目には整数 M が書かれており，IOI 語の規則の個数が M であることを表す．
続く M 行には IOI 語の規則の情報が書かれている．i + 3 行目 (1 ≤ i ≤ M) には，規則 i を表す A から Z までの文字 Ai, Bi が空白を区切りとして書かれている．Ai = Aj かつ Bi = Bj なる規則 j (j ≠ i) は存在しない．

標準出力に考えられる原文の個数を 10 000 000 で割った余りを 1 行で出力せよ．