24099번 - 解読 (Deciphering) 다국어

문제

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

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

規則 i (1 ≤ i ≤ M):文字 A_i の直後に文字 B_i は来ない.

与えられた機密文書の原文として考えられるものの個数を 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 までの文字 A_i, B_i が空白を区切りとして書かれている.A_i = A_j かつ B_i = B_j なる規則 j (j ≠ i) は存 在しない.

출력

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

제한

• 1 ≤ L ≤ 300 000 機密文書の長さ
• 0 ≤ M ≤ 26 × 26 IOI 語の規則の個数

힌트