Language: C++

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
#include <functional>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define rep1(i,n) for(int i=1;i<=(n);++i)
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define MAX_W 501
#define MAX_M 500
#define MAX_ps 600
vector<string> pre;
int mod=1e9+7;
int N,M,K;
int a[21][MAX_ps][MAX_W],b[21][MAX_ps][MAX_W];	//len,suffix,last word
int ne[MAX_ps][MAX_W];
bool appear[MAX_ps][MAX_W],twice[MAX_ps][MAX_W],can[MAX_ps][MAX_W];
string from[250],to[250],s[30];
vector<string> words;
vector<int> G[MAX_W];
vector<int> cans[MAX_ps];
inline int wordid(string s){
	return lower_bound(all(words),s)-words.begin();
}
int main(){
	while(true){
		cin>>N>>M>>K;
		if(N==0) break;
		pre.clear();
		words.clear();
		rep(i,N){
			cin>>from[i]>>to[i];
			words.pb(from[i]);
			words.pb(to[i]);
		}
		words.pb("");
		sort(all(words));
		words.erase(unique(all(words)),words.end());
		rep(i,words.size()) G[i].clear();
		rep(i,N){
			G[wordid(from[i])].pb(wordid(to[i]));
		}
		rep1(i,words.size()-1) G[0].pb(i);
		rep(i,K) cin>>s[i];
		sort(s,s+K);
		rep(i,K){
			rep(j,s[i].size()+1) pre.pb(s[i].substr(0,j));
		}
		sort(all(pre));
		pre.erase(unique(all(pre)),pre.end());
		int ps=pre.size(),ws=words.size();
		rep(i,ps) rep(j,ws) can[i][j]=false;
		rep(i,ps) cans[i].clear();
		rep(i,ps){
			string x=pre[i];
			rep(j,ws){
				string st=x+words[j];
				int k;
				while(true){
					k=lower_bound(all(pre),st)-pre.begin();
					if(k<ps&&pre[k]==st) break;
					st=st.substr(1);
				}
				ne[i][j]=k;
				can[k][j]=true;
				appear[i][j]=false;
				twice[i][j]=false;
				st=x;
				int cnt=0;
				rep(h,words[j].size()){
					st+=words[j][h];
					rep(p,K) if(st.size()>=s[p].size()&&st.substr(st.size()-s[p].size())==s[p]) cnt++;
					if(cnt>=2) break;
				}
				if(cnt>=1) appear[i][j]=true;
				if(cnt>=2) twice[i][j]=true;
//				if(appear[i][j]) printf("i=%d,j=%d\n",i,j);
			}
		}
		rep(i,ps) rep(j,ws) if(can[i][j]) cans[i].pb(j);
		rep(i,21) rep(j,ps) rep(k,ws) a[i][j][k]=b[i][j][k]=0;
		b[0][0][0]=1;
		rep(i,M){
			int i21=i%21;
			rep(j,ps){
				for(int k:cans[j]){
					for(int u : G[k]){
						if(twice[j][u]) continue;
						int ni=i+words[u].size();
						if(ni>M) continue;
						int ni21=i21+words[u].size();
						if(ni21>=21) ni21-=21;
						if(appear[j][u]){
							a[ni21][ne[j][u]][u]+=b[i21][j][k];
							if(a[ni21][ne[j][u]][u]>=mod) a[ni21][ne[j][u]][u]-=mod;
						}else{
							a[ni21][ne[j][u]][u]+=a[i21][j][k];
							if(a[ni21][ne[j][u]][u]>=mod) a[ni21][ne[j][u]][u]-=mod;
							b[ni21][ne[j][u]][u]+=b[i21][j][k];
							if(b[ni21][ne[j][u]][u]>=mod) b[ni21][ne[j][u]][u]-=mod;
						}
					}
				}
			}
			rep(j,ps) for(int k:cans[j]) a[i21][j][k]=b[i21][j][k]=0;
		}
		int ans=0;
		rep(i,ps) rep(j,ws) add(ans,a[M%21][i][j]);
		cout<<ans<<endl;
	}
}

Compiler output:
a.cc: In function 'int main()':
a.cc:115:37: error: 'add' was not declared in this scope; did you mean 'fadd'?
  115 |                 rep(i,ps) rep(j,ws) add(ans,a[M%21][i][j]);
      |                                     ^~~
      |                                     fadd