해독 (Deciphering)

당신은 A부터 Z까지의 문자로 쓰인 IOI국의 기밀 문서를 손에 넣었다. 이 기밀 문서의 원문은 IOI어로 쓰여 있다. 기밀 문서에서 몇 개의 문자(0개여도 된다)를 지우면 원문을 얻을 수 있다.

IOI어의 문장은 1자 이상으로 이루어진 문자열이며, 서로 다른 M개의 다음 조건을 만족한다:

규칙 i (1 ≤ i ≤ M): 문자 Ai 바로 뒤에 문자 Bi는 오지 않는다.

주어진 기밀 문서의 원문으로 가능한 것의 개수를 10 000 000으로 나눈 나머지를 구하시오. 단, 지우는 방법이 달라도 같은 원문이면 하나로 센다.

기밀 문서에서 가능한 원문의 개수를 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줄로 출력하라.

• 1 ≤ L ≤ 300 000, 기밀 문서의 길이
• 0 ≤ M ≤ 26 × 26, IOI어의 규칙의 개수