Sakura Poetry

Nathan O. Davis is a student in an integrated circuits program.

To make up for missing credits, Nathan is taking a course on Japanese culture. Today's assignment is to write poetry.

Nathan has studied too little and is poor at Japanese, so he decided to have a program generate poems for him. First he obtained a dictionary of Japanese word connections. After that, all he has to do is generate random text that follows the word connections.

However, not every randomly generated string is accepted as a poem. A poem must contain exactly one of the season words, appearing exactly once. A season word may not appear twice or more, and two or more kinds of season words may not each appear once. A season word may also appear across the boundary between connected words.

Your job is to write a program that, given the word connection dictionary and the list of season words in the input, counts how many poems of the specified length can be made. If the same string is obtained as a poem by joining different words, those are counted separately. The answer can be very large, so print it modulo 1,000,000,007.

The input contains multiple test cases. One test case has the following format.

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

The first line of the input contains three integers N (1 ≤ N ≤ 250), M (1 ≤ M ≤ 500), K (1 ≤ K ≤ 30), which are the size of the word connection dictionary, the length of the poem to be made, and the number of season words.

The following N lines describe the word connection dictionary. Each line contains two strings fromi, toi, meaning that the word toi may appear immediately after the word fromi. Note that this does not mean fromi may appear immediately after toi. It also does not mean toi may appear immediately after some other string ending in fromi. A poem may start with any word contained in the connection dictionary. The following K lines each consist of one string seasonwordi and represent a season word. Every string appearing in the input consists of lowercase letters and has length between 1 and 20. Each entry of the connection dictionary and each season word is distinct. That is, for i ≠ j, fromi ≠ fromj or toi ≠ toj. Likewise, for i ≠ j, seasonwordi ≠ seasonwordj. The end of the input is marked by three zeros.

Print the number of distinct poems that can be generated, modulo 1,000,000,007, on one line. As stated above, if the same string is obtained as a poem by joining different words, those are counted separately. Strictly speaking, when two poems s, t are obtained by concatenating the word sequences [a1, a2, ..., an] and [b1, b2, ..., bm] in order, the two poems s, t are considered the same poem if and only if n = m and ai = bi for all 1 ≤ i ≤ n.