JSOI交给队员ZYX一个任务，编制一个称之为“文本生成器”的电脑软件：该软件的使用者是一些低幼人群，他们现在使用的是GW文本生成器v6版。该软件可以随机生成一些文章―――总是生成一篇长度固定且完全随机的文章—— 也就是说，生成的文章中每个字节都是完全随机的。如果一篇文章中至少包含使用者们了解的一个单词，那么我们说这篇文章是可读的（我们称文章a包含单词b，当且仅当单词b是文章a的子串）。但是，即使按照这样的标准，使用者现在使用的GW文本生成器v6版所生成的文章也是几乎完全不可读的?。ZYX需要指出GW文本生成器 v6生成的所有文本中可读文本的数量，以便能够成功获得v7更新版。你能帮助他吗？

　　输入文件的第一行包含两个正整数，分别是使用者了解的单词总数N (<= 60)，GW文本生成器 v6生成的文本固定长度M；以下N行，每一行包含一个使用者了解的单词。这里所有单词及文本的长度不会超过100，并且只可能包含英文大写字母A..Z

　　一个整数，表示可能的文章总数。只需要知道结果模10007的值。

  1 //It is made by wfj_2048~  2 #include <algorithm>  3 #include <iostream>  4 #include <complex>  5 #include <cstring>  6 #include <cstdlib>  7 #include <cstdio>  8 #include <vector>  9 #include <cmath> 10 #include <queue> 11 #include <stack> 12 #include <map> 13 #include <set> 14 #define rhl (10007) 15 #define inf (1<<30) 16 #define N (10010) 17 #define il inline 18 #define RG register 19 #define ll long long 20 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) 21  22 using namespace std; 23  24 int f[110][N],q[N],n,m,len,ans; 25 char s[N]; 26  27 struct AC_auto{ 28  29     int ch[N][26],val[N],nxt[N],last[N],sz; 30  31     il void insert(char *s,RG int len){ 32     RG int x=0,c; 33     for (RG int i=1;i<=len;++i){ 34         c=s[i]-65; 35         if (!ch[x][c]) ch[x][c]=++sz; 36         x=ch[x][c]; 37     } 38     val[x]++; return; 39     } 40      41     il void build(){ 42     RG int h=0,t=0; 43     for (RG int c=0;c<26;++c) 44         if (ch[0][c]) nxt[ch[0][c]]=last[ch[0][c]]=0,q[++t]=ch[0][c]; 45     while (h<t){ 46         RG int x=q[++h],v,j; 47         for (RG int c=0;c<26;++c){ 48         v=ch[x][c]; if (!v){ ch[x][c]=ch[nxt[x]][c]; continue; } 49         q[++t]=v,nxt[v]=last[v]=0,j=nxt[x]; while (j && !ch[j][c]) j=nxt[j]; 50         nxt[v]=ch[j][c],last[v]=val[nxt[v]] ? nxt[v] : last[nxt[v]]; 51         } 52     } 53     return; 54     } 55      56 }AC; 57  58 il int gi(){ 59     RG int x=0,q=1; RG char ch=getchar(); 60     while ((ch<‘0‘ || ch>‘9‘) && ch!=‘-‘) ch=getchar(); 61     if (ch==‘-‘) q=-1,ch=getchar(); 62     while (ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-48,ch=getchar(); 63     return q*x; 64 } 65  66 il int qpow(RG int a,RG int b){ 67     RG int ans=1; 68     while (b){ 69     if (b&1) ans=ans*a%rhl; 70     a=a*a%rhl,b>>=1; 71     } 72     return ans; 73 } 74  75 il void work(){ 76     n=gi(),m=gi(); 77     for (RG int i=1;i<=n;++i){ 78     scanf("%s",s+1); 79     len=strlen(s+1); 80     AC.insert(s,len); 81     } 82     AC.build(); f[0][0]=1; 83     for (RG int i=0;i<m;++i) 84     for (RG int j=0;j<=AC.sz;++j){ 85         if (!f[i][j]) continue; 86         for (RG int k=0;k<26;++k){ 87         if (AC.val[AC.ch[j][k]] || AC.last[AC.ch[j][k]]) continue; 88         f[i+1][AC.ch[j][k]]+=f[i][j]; 89         if (f[i+1][AC.ch[j][k]]>=rhl) f[i+1][AC.ch[j][k]]-=rhl; 90         } 91     } 92     for (RG int i=0;i<=AC.sz;++i){ ans+=f[m][i]; if (ans>=rhl) ans-=rhl; } 93     printf("%d\n",(qpow(26,m)-ans+rhl)%rhl); return; 94 } 95  96 int main(){ 97     File("txt"); 98     work(); 99     return 0;100 }