dp[i][j][0]代表当前匹配到i号点走了j步且没到过单词节点，1代表到过，直接转移。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define mod 10007
#define N 6005
using namespace std;
int ch[N][];int cnt;int f[N];
int n,m;
char s[];
bool ok[N];
void in()
{
int l=strlen(s);int now=;
for(int i=;i<l;i++)
{
int y=s[i]-'A';
if(!ch[now][y])ch[now][y]=++cnt;
now=ch[now][y];
}
ok[now]=;
}
queue<int>q;
void fail()
{
for(int i=;i<;i++)
{
if(ch[][i])
{
q.push(ch[][i]);
}
}
while(!q.empty())
{
int tmp=q.front();q.pop();
for(int i=;i<;i++)
{
int u=ch[tmp][i];
if(!u)
{
ch[tmp][i]=ch[f[tmp]][i];continue;
}
q.push(u);f[u]=ch[f[tmp]][i];
if(ok[f[u]])ok[u]=;
}
}
}
int dp[][][];
void dpp()
{
dp[][][]=;
for(int i=;i<m;i++)
{
for(int j=;j<=cnt;j++)
{
for(int k=;k<;k++)
{
if(ok[ch[j][k]])
{
dp[ch[j][k]][i+][]+=(dp[j][i][]+dp[j][i][]);
dp[ch[j][k]][i+][]%=mod;
}
else
{
dp[ch[j][k]][i+][]+=dp[j][i][];dp[ch[j][k]][i+][]%=mod;
dp[ch[j][k]][i+][]+=dp[j][i][];dp[ch[j][k]][i+][]%=mod;
}
}
}
}
return ;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
{
scanf("%s",s);in();
}
fail();
dpp();
int ans=;
for(int i=;i<=cnt;i++)
{
ans=(ans+dp[i][m][])%mod;
}
cout<<ans<<endl;
return ;
}