考虑建出 AC 自动机，朴素做法是高斯消元，\(f_i=\sum\limits_{j=0}^{k-1}f_{to_{i,j}}p_j+1\)，复杂度 \(O(n^3m^3)\)，不能接受。
考虑优化高斯消元的过程，我们定义以下节点为“关键点”：
- 根节点
- 对于一个 trie 树（也就是未经过 AC 自动机
getfail操作得到的树）上有超过两个儿子的节点 \(x\)，其所有儿子均为关键点。
我们考虑将所有节点表示为 \(\sum\limits_{j=1}^ccoef_{i,j}f_{pt_j}+coef_{i,c+1}\) 的形式，其中 \(c\) 为关键点个数，\(pt_j\) 为第 \(j\) 个关键点。具体方法是，对于一个在原 trie 树上有恰好一个儿子的儿子的节点 \(i\)，其会有恰好一个儿子在 trie 树上深度比其大，记其为 \(son\)，我们将含 \(f_{son}\) 的项移到一侧，其他项移到另一侧，这样就由 \(coef_{i}\) 转移得到 \(coef_{son}\)。直接在原树上 bfs 进行这个操作即可。
显然这样相当于用树上高斯消元的技巧手动消掉了所有恰好有一个儿子的点的项，这样继续对那些有 \(\ge 2\) 或 \(0\) 个儿子的节点跑三方的高斯消元解出所有关键点的 \(f\) 即可。显然，我们添加一个字符串时，最多只会多出一个儿子个数 \(\ge 2\) 的点，而且显然关键点个数的增量等于儿子个数 \(\ge 2\) 的点的增量与叶子节点个数的增量之和，也就是说变量个数等于方程个数且不超过 \(2n\)，所以时间复杂度是可以接受的。
const int MAXN=200;
const int MAXP=1e4;
const int MOD=1e9+7;
const int INV100=570000004;
int qpow(int x,int e){int ret=1;for(;e;e>>=1,x=1ll*x*x%MOD)if(e&1)ret=1ll*ret*x%MOD;return ret;}
int n,m,k,p[28];string s[MAXN+5];char buf[MAXP+5];
int f[MAXP+5][MAXN+5],g[MAXN+5][MAXN+5],h[MAXN+5],res[MAXP+5],cnt;
namespace AC_Automaton{
int ch[MAXP+5][28],tr[MAXP+5][28],ncnt,ed[MAXP+5],fail[MAXP+5],fa[MAXP+5],id[MAXP+5],idcnt;
void insert(string ss){
int cur=0;
for(int i=0;i<ss.size();i++){
if(!ch[cur][ss[i]-'a'])ch[cur][ss[i]-'a']=++ncnt,fa[ncnt]=cur;
cur=ch[cur][ss[i]-'a'];
}ed[cur]=1;
}
void getfail(){
queue<int>q;
for(int i=0;i<k;i++)if(ch[0][i])tr[0][i]=ch[0][i],q.push(tr[0][i]);
while(!q.empty()){
int x=q.front();q.pop();
for(int i=0;i<k;i++){
if(ch[x][i])tr[x][i]=ch[x][i],fail[tr[x][i]]=tr[fail[x]][i],q.push(tr[x][i]);
else tr[x][i]=tr[fail[x]][i];
}
}
}
void init(){
getfail();id[0]=++idcnt;
for(int i=0;i<=ncnt;i++){
int son=0;
for(int j=0;j<k;j++)if(ch[i][j])++son;
if(son>=2){
for(int j=0;j<k;j++)if(ch[i][j])
id[ch[i][j]]=++idcnt;
}
}
// for(int i=0;i<=ncnt;i++)printf("%d%c",fail[i]," \n"[i==ncnt]);
// for(int i=0;i<=ncnt;i++)printf("%d%c",id[i]," \n"[i==ncnt]);
// for(int i=0;i<=ncnt;i++)for(int j=0;j<k;j++)printf("%d%c",tr[i][j]," \n"[j==k-1]);
queue<int>q;q.push(0);
while(!q.empty()){
int x=q.front();q.pop();
if(id[x])f[x][id[x]]=1;
else{
for(int i=1;i<=idcnt+1;i++)f[x][i]=f[fa[x]][i];
int P=0;
for(int i=0;i<k;i++){
if(tr[fa[x]][i]!=x){
for(int j=1;j<=idcnt+1;j++)
f[x][j]=(f[x][j]+1ll*(MOD-p[i])*f[tr[fa[x]][i]][j])%MOD;
}else{
assert(!P);
P=qpow(p[i],MOD-2);
}
}
f[x][idcnt+1]=(f[x][idcnt+1]+MOD-1)%MOD;
for(int i=1;i<=idcnt+1;i++)f[x][i]=1ll*f[x][i]*P%MOD;
}
for(int i=0;i<k;i++)if(ch[x][i])q.push(ch[x][i]);
}
// for(int i=0;i<=ncnt;i++)for(int j=1;j<=idcnt+1;j++)printf("%d%c",f[i][j]," \n"[j==idcnt+1]);
for(int i=0;i<=ncnt;i++){
int son=0;
for(int j=0;j<k;j++)if(ch[i][j])++son;
if(son>=2){
++cnt;
for(int j=1;j<=idcnt+1;j++)g[cnt][j]=f[i][j];
for(int j=0;j<k;j++)for(int l=1;l<=idcnt+1;l++)
g[cnt][l]=(g[cnt][l]+1ll*(MOD-p[j])*f[tr[i][j]][l])%MOD;
g[cnt][idcnt+1]=MOD-g[cnt][idcnt+1];
g[cnt][idcnt+1]=(g[cnt][idcnt+1]+1)%MOD;
}else if(ed[i]){
++cnt;
for(int j=1;j<=idcnt+1;j++)g[cnt][j]=f[i][j];
g[cnt][idcnt+1]=MOD-g[cnt][idcnt+1];
}
}
}
}using namespace AC_Automaton;
void Gauss(){
assert(cnt==idcnt);
for(int i=1;i<=cnt;i++){
int t=0;
for(int j=i;j<=cnt;j++)if(g[j][i])t=j;
for(int j=i;j<=idcnt+1;j++)swap(g[i][j],g[t][j]);
int iv=qpow(g[i][i],MOD-2);
for(int j=i;j<=idcnt+1;j++)g[i][j]=1ll*g[i][j]*iv%MOD;
for(int j=i+1;j<=cnt;j++){
for(int k=i+1;k<=idcnt+1;k++)g[j][k]=(g[j][k]+1ll*(MOD-g[j][i])*g[i][k])%MOD;
g[j][i]=0;
}
}
for(int i=cnt;i;i--){
h[i]=g[i][idcnt+1];
for(int j=i+1;j<=idcnt;j++)h[i]=(h[i]+1ll*(MOD-h[j])*g[i][j])%MOD;
}
}
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i=0;i<k;i++)scanf("%d",&p[i]),p[i]=1ll*p[i]*INV100%MOD;
for(int i=1;i<=n;i++){
scanf("%s",buf+1);
for(int j=1;j<=m;j++)s[i].pb(buf[j]);
insert(s[i]);
}
init();Gauss();
for(int i=0;i<=ncnt;i++){
res[i]=f[i][idcnt+1];
for(int j=1;j<=idcnt;j++)res[i]=(res[i]+1ll*h[j]*f[i][j])%MOD;
}
scanf("%s",buf+1);bool flg=0;int cur=0,len=strlen(buf+1);
for(int i=1;i<=len;i++){
cur=tr[cur][buf[i]-'a'];flg|=ed[cur];
if(flg)printf("%d\n",i);
else printf("%d\n",(i+res[cur])%MOD);
}
return 0;
}
/*
4 4 4
10 20 30 40
cabc
abcb
abbb
cccc
ababacabaabcca
*/
/*
1 37 17
7 8 5 9 2 5 5 6 8 7 4 6 7 5 4 8 4
eplpljcadqaoebbgkdabfodaekoepjafgfodb
*/