aoj-2257.cpp

#include "../include/string/aho_corasick.cpp"
#include "../include/types/mod.cpp"

using namespace std;

#define REP(i, n) for (int i = 0; i < (int)(n); i++)

using Mod = Modulo<1000000007, true>;

map<string, int> dict_memo;
vector<string> dict_str;

int dict(const string &s) {
  if (dict_memo.count(s)) return dict_memo[s];
  int res = dict_str.size();
  dict_str.push_back(s);
  return dict_memo[s] = res;
}

const int BLOCK = 21;

vector<int> g[512];
Mod dp[BLOCK][512][610][2];
int is_match[512][610];
int next_node[512][610];

int main() {
  int N, M, K;
  while (cin >> N >> M >> K, N) {
    REP(i, 512) g[i].clear();
    dict_str.clear();
    dict_memo.clear();
    memset(is_match, 0, sizeof(is_match));
    memset(dp, 0, sizeof(dp));
    memset(next_node, 0, sizeof(next_node));
    vector<string> season(K);
    REP(i, N) {
      string s, t;
      cin >> s >> t;
      g[dict(s)].push_back(dict(t));
    }
    const int n = dict_str.size();
    REP(i, n) g[n].push_back(i);
    REP(i, K) cin >> season[i];
    AhoCorasick<State> aho(season);
    REP(i, dict_str.size()) REP(j, aho.pma.size()) {
      int index = j;
      for (char c : dict_str[i]) {
        index = aho.next(index, c);
        is_match[i][j] += aho.pma[index].accept.size();
      }
      next_node[i][j] = index;
    }
    REP(i, BLOCK) REP(j, 512) REP(k, 610) REP(l, 2) dp[i][j][k][l] = 0;
    dp[0][n][0][0] = 1;
    REP(i, M) {
      int src = i % BLOCK;
      REP(from, n + 1) REP(k, aho.pma.size()) {
        for (int to : g[from]) {
          int dest = (src + int(dict_str[to].size())) % BLOCK;
          if (is_match[to][k] >= 2) continue;
          if (is_match[to][k]) {
            dp[dest][to][next_node[to][k]][1] += dp[src][from][k][0];
          }
          else {
            dp[dest][to][next_node[to][k]][0] += dp[src][from][k][0];
            dp[dest][to][next_node[to][k]][1] += dp[src][from][k][1];
          }
        }
      }
      REP(j, n + 1) REP(k, aho.pma.size()) REP(l, 2) dp[src][j][k][l] = 0;
    }
    Mod res = 0;
    REP(j, n + 1) REP(k, aho.pma.size()) res += dp[M % BLOCK][j][k][1];
    cout << int(res) << endl;
  }
  return 0;
}