English text is not available in this practice contest.

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

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

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

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

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

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

N M K
from₁ to₁
from₂ to₂
:
from_N to_N
seasonword₁
seasonword₂
:
seasonword_K

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

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

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

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

1
1
3
715991824
1
1