사쿠라 시

Nathan O. Davis는 집적회로 과정의 학생이다.

Nathan은 부족한 학점을 채우기 위해 일본 문화에 관한 수업을 듣고 있다. 오늘 과제는 시를 짓는 것이다.

공부가 부족해 일본어에 서툰 Nathan은 프로그램으로 시를 자동 생성하기로 했다. 우선 그는 일본어 단어의 연결 사전을 구했다. 이제 단어의 연결에 따라 무작위로 문장을 생성하기만 하면 된다.

하지만 무작위로 생성된 모든 문자열이 시로 인정되는 것은 아니다. 시에는 몇 가지 계절어 중 하나가 정확히 한 번 나타나야 한다. 어떤 계절어가 두 번 이상 나타나거나, 두 종류 이상의 계절어가 각각 한 번씩 나타나는 것은 허용되지 않는다. 계절어는 단어 연결의 경계를 넘어 나타나도 된다.

당신의 일은 입력으로 주어진 단어 연결 사전과 계절어 목록에서 지정된 길이의 시가 몇 가지로 만들어지는지 구하는 프로그램을 작성하는 것이다. 서로 다른 단어를 이어 붙여 시가 되는 같은 문자열이 만들어졌다면, 그것들은 중복해서 세야 한다. 답이 매우 커질 수 있으므로 1,000,000,007로 나눈 나머지를 출력하라.

입력은 여러 테스트 케이스를 포함한다. 한 테스트 케이스는 다음 형식으로 주어진다.

N M K
from1 to1
from2 to2
:
fromN toN
seasonword1
seasonword2
:
seasonwordK

입력의 첫 줄에는 세 정수 N (1 ≤ N ≤ 250), M (1 ≤ M ≤ 500), K (1 ≤ K ≤ 30)가 있고, 각각 단어 연결 사전의 크기, 만들어야 할 시의 길이, 계절어의 수를 나타낸다.

이어지는 N 줄은 단어 연결 사전의 정보를 나타낸다. 각 줄은 두 문자열 fromi, toi를 포함하고, 단어 fromi 뒤에 이어서 단어 toi가 나타나도 된다는 뜻이다. toi 뒤에 이어서 fromi가 나타나도 된다는 뜻은 아니다. 또한 fromi로 끝나는 다른 문자열 뒤에 이어서 toi가 나타나도 된다는 뜻도 아니다. 시는 연결 사전에 포함된 어떤 단어에서든 시작할 수 있다. 이어지는 K 줄은 문자열 seasonwordi 하나로 이루어지고, 각각 계절어를 나타낸다. 입력에 나타나는 문자열은 모두 소문자 알파벳으로 이루어지고, 길이는 1 이상 20 이하이다. 연결 사전의 각 항목과 계절어는 서로 다르다. 즉 i ≠ j에 대해 fromi ≠ fromj 또는 toi ≠ toj가 성립한다. 마찬가지로 i ≠ j에 대해 seasonwordi ≠ seasonwordj가 성립한다. 입력의 끝에는 입력의 끝을 나타내는 세 개의 0이 있다.

생성되는 서로 다른 시의 수를 1,000,000,007로 나눈 나머지를 한 줄에 출력하라. 앞서 말했듯이 서로 다른 단어를 이어 붙여 시가 되는 같은 문자열이 만들어졌다면, 그것들은 중복해서 세야 한다. 엄밀히 말해 두 시 s, t가 각각 단어의 열 [a1, a2, ..., an], [b1, b2, ..., bm]을 차례로 이어 붙여 얻어진 것일 때, n = m이고 모든 1 ≤ i ≤ n에 대해 ai = bi인 경우에만, 그리고 그때만 두 시 s, t는 같은 시로 본다.