【BZOJ】【1030】【JSOI2007】文本生成器

/**************************************************************
Problem: 1030
User: Tunix
Language: C++
Result: Accepted
Time:208 ms
Memory:7148 kb
****************************************************************/ //BZOJ 1030
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
using namespace std;
inline int getint(){
int v=,sign=; char ch=getchar();
while(ch<''||ch>''){ if (ch=='-') sign=-; ch=getchar();}
while(ch>=''&&ch<=''){ v=v*+ch-''; ch=getchar();}
return v*sign;
}
const int N=,INF=~0u>>;
typedef long long LL;
/******************tamplate*********************/
const int MOD=;
int n,m,cnt=;
struct Trie{
int ch[],cnt,fail;
bool sign;
}T[N];
inline int id(char c){return c-'A';}
void ins(char *s){
int x=,y;
rep(i,strlen(s)){
y=id(s[i]);
if (T[x].ch[y]==)
T[x].ch[y]=++cnt;
x=T[x].ch[y];
}
T[x].sign=;
}
int Q[N];
void make_fail(){
int l=,r=-;
Q[++r]=;
while(l<=r){
int x=Q[l++],y,j;
rep(i,){
j=T[x].fail;
while(j && !T[j].ch[i]) j=T[j].fail;
if (T[x].ch[i]){
y=T[x].ch[i];
T[y].fail=j ? T[j].ch[i] : ;
T[y].sign=T[y].sign|T[T[y].fail].sign;
Q[++r]=y;
}else T[x].ch[i]=j ? T[j].ch[i] : ;
}
}
}
int f[][N][];
void dp(){
f[][][]=;
rep(i,m) F(j,,cnt) rep(k,) F(l,,)
if(T[T[j].ch[k]].sign)
(f[i+][T[j].ch[k]][]+=f[i][j][l])%=MOD;
else (f[i+][T[j].ch[k]][l]+=f[i][j][l])%=MOD;
}
char s[N];
int main(){
#ifndef ONLINE_JUDGE
freopen("1030.in","r",stdin);
freopen("1030.out","w",stdout);
#endif
n=getint(); m=getint();
F(i,,n){
scanf("%s",s);
ins(s);
}
make_fail();
dp();
int ans=;
F(i,,cnt) (ans+=f[m][i][])%=MOD;
printf("%d\n",ans);
return ;
}