#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

class PMA
{
    int n;
    vector<vector<int> > next;
    vector<bitset<32> > match;
    vector<int> failure;
public:
    PMA(const vector<string>& pattern){
        next.assign(1, vector<int>(128, -1));
        match.assign(1, 0);
        for(unsigned i=0; i<pattern.size(); ++i){
            int curr = 0;
            for(unsigned j=0; j<pattern[i].size(); ++j){
                if(next[curr][pattern[i][j]] == -1){
                    next[curr][pattern[i][j]] = next.size();
                    next.push_back(vector<int>(128, -1));
                    match.push_back(0);
                }
                curr = next[curr][pattern[i][j]];
            }
            match[curr][i] = true;
        }

        n = next.size();
        failure.resize(n, 0);
        vector<int> node1(1, 0);
        while(!node1.empty()){
            vector<int> node2;
            for(unsigned i=0; i<node1.size(); ++i){
                for(int j=0; j<128; ++j){
                    int s = node1[i];
                    if(next[s][j] == -1)
                        continue;
                    node2.push_back(next[s][j]);
                    int t = s;
                    while(t != 0){
                        if(next[failure[t]][j] != -1){
                            failure[next[s][j]] = next[failure[t]][j];
                            match[next[s][j]] |= match[next[failure[t]][j]];
                            break;
                        }
                        t = failure[t];
                    }
                }
            }
            node1.swap(node2);
        }
    }
    int size(){
        return n;
    }
    int transition(int curr, char c){
        if(next[curr][c] != -1)
            return next[curr][c];
        if(curr == 0)
            return 0;
        return transition(failure[curr], c);
    }
    bitset<32> checkMatch(int curr){
        return match[curr];
    }
};

const int MOD = 1000000007;

int main()
{
    for(;;){
        int n, m, p;
        cin >> n >> m >> p;
        if(n == 0)
            return 0;

        map<string, int> index;
        index.insert(make_pair("", 0));
        vector<string> word(1, "");
        vector<vector<int> > connect(1);
        for(int i=0; i<n; ++i){
            string from, to;
            cin >> from >> to;
            int j, k;
            if(index.find(from) == index.end()){
                j = index.size();
                index[from] = j;
                word.push_back(from);
                connect.resize(connect.size()+1);
            }else{
                j = index[from];
            }
            if(index.find(to) == index.end()){
                k = index.size();
                index[to] = k;
                word.push_back(to);
                connect.resize(connect.size()+1);
            }else{
                k = index[to];
            }
            connect[j].push_back(k);
        }
        n = index.size();
        for(int i=1; i<n; ++i)
            connect[0].push_back(i);

        vector<string> season(p);
        for(int i=0; i<p; ++i)
            cin >> season[i];
        PMA pma(season);
        p = pma.size();

        vector<vector<int> > seasonNum(p, vector<int>(n, 0));
        vector<vector<int> > next(p, vector<int>(n));
        for(int i=0; i<p; ++i){
            for(int j=0; j<n; ++j){
                next[i][j] = i;
                for(unsigned k=0; k<word[j].size(); ++k){
                    next[i][j] = pma.transition(next[i][j], word[j][k]);
                    seasonNum[i][j] += pma.checkMatch(next[i][j]).count();
                }
            }
        }

        map<pair<pair<int, int>, pair<int, int> >, int> num;
        num[make_pair(make_pair(0, 0), make_pair(0, 0))] = 1;
        int ret = 0;
        while(!num.empty()){
            int a = num.begin()->first.first.first;   // ¶
            int b = num.begin()->first.first.second;  // ÅãÌPê
            int c = num.begin()->first.second.first;  // PMAÌJÚ}É¨¯éÊu
            int d = num.begin()->first.second.second; // GêÌ
            int x = num.begin()->second;
            num.erase(num.begin());

            for(int i=0; i<connect[b].size(); ++i){
                int b2 = connect[b][i];
                int a2 = a + word[b2].size();
                if(a2 > m)
                    continue;
                int c2 = next[c][b2];
                int d2 = d + seasonNum[c][b2];
                if(d2 > 1)
                    continue;

                if(a2 == m){
                    if(d2 == 1){
                        ret += x;
                        ret %= MOD;
                    }
                }else{
                    (num[make_pair(make_pair(a2, b2), make_pair(c2, d2))] += x) %= MOD;
                }
            }
        }

        cout << ret << endl;
    }
}

Measured memory_bytes: 3688