Sakura Poetry

時間制限 : 8 sec, メモリ制限 : 65536 KB

桜詩 願はくは花の下にて春死なむ

English text is not available in this practice contest.

Nathan O. Davis は集積回路コースの学生である.

Nathan は足りない単位を補充するために,日本文化に関する授業を履修している.今日の課題は詩の作成である.

Nathan は勉強不足で日本語が不得手なため,プログラムに詩を自動生成させようと考えた.手始めに彼は,日本語の単語の接続辞書を入手した. あとは単語の接続にしたがってランダムな文章を生成するだけである.

しかしながら,ランダムに生成された全ての文字列が詩として認められるわけではない. 詩には,いくつかの季語のうち1つが,一度だけ現れていなければならない.ある季語が2回以上出現することや,2種類以上の季語が1回ずつ出現することは許されない. また,季語は単語の接続の境界をまたいで出現してもよい.

あなたの仕事は,入力で与えられた単語の接続辞書と季語のリストから,指定された長さの詩が何通りに作られるかを求めるプログラムを作成することである. 違う単語を繋げて詩となる同じ文字列が得られた場合,それらは重複して数え上げるものとする.答えは非常に大きくなりうるので, 1,000,000,007 で割った余りを出力せよ.

Input

入力は複数のテストケースを含んでいる.1つのテストケースは,以下の形式で与えられる.

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

入力の最初の行には3つの整数 N (1 ≤ N ≤ 250), M (1 ≤ M ≤ 500), K (1 ≤ K ≤ 30) が含まれ,それぞれ単語の接続辞書の大きさ,作成すべき詩の長さ,季語の数を表す.

続く N 行は単語の接続辞書の情報を表す. 各行は2つの文字列 fromi , toi を含み,単語 fromi の後に続けて単語 toi が出現してもよいということを表す. toi の後に続けて fromi が出現してもよいということを表すものではないことに注意せよ.また,fromi で終わるような他の文字列の後に続けて toi が出現してもよいということを表すものでもない.詩は,接続辞書に含まれるどの単語から始めてもよい. 続く K 行は1つの文字列 seasonwordi からなり,それぞれ季語を表す. 入力中に現れる文字列は全て小文字のアルファベットからなり,その長さは 1 以上 20 以下である. 接続辞書の各項目,および季語は互いに異なる. すなわち, ij に対して fromifromj または toitoj が成り立つ. 同様に,ij に対して seasonwordiseasonwordj が成り立つ. 入力の末尾には,入力の終了を表す 3 つの 0 がある.

Output

生成される異なる詩の数を 1,000,000,007 で割った余りを1行に出力せよ. 先に言及したように,違う単語を繋げて詩となる同じ文字列が得られた場合,それらは重複して数え上げるものとする. 厳密に言えば,2つの詩 s, t があり,それぞれ単語の列 [a1 , a2 , ..., an ], [b1 , b2 , ..., bm ] を順に連結して得られたものであるとき, n = m かつすべての 1 ≤ in に対して ai = bi であるとき,またそのときに限って,2つの詩 s, t は同一の詩とみなされる.

Sample Input

4 64 2
negawakuha hananoshitanite
hananoshitanite harushinan
harushinan sonokisaragino
sonokisaragino mochizukinokoro
sakura
hana
2 15 2
naha naha
naha gachoon
sakura
hana
3 7 2
asakur a
a sakura
asa kura
sakura
hana
9 100 2
a a
a h
a n
h a
h h
h n
n a
n h
n n
sakura
hana
4 2 2
a a
a b
b a
b b
ab
b
4 7 4
i cpc
mi cp
ac mi
cp c
ac
wa
tle
re
0 0 0

Output for the Sample Input

1
1
3
715991824
1
1

Source: ACM International Collegiate Programming Contest , ACM-ICPC Japan Alumni Group Practice Contest for Japan Domestic 2011, 2011-06-12
http://acm-icpc.aitea.net/