1 const maxn=6419; 2  maxs=25; 3  vv=10007; 4 var 5  next:array[0..maxn,0..maxs] of longint; 6  pd:array[0..maxn] of boolean; 7  f:array[0..maxn] of longint; 8  q:array[0..maxn] of longint; 9  dp:array[0..maxn,0..105] of longint;10  s:string;11  head,tail,root,n,m,tot:longint;12 13 procedure push(x:longint); begin inc(tail); q[tail]:=x; end;14 15 function new:longint;16 var i:longint;17 begin18  pd[tot]:=false;19  for i:= 0 to maxs do next[tot,i]:=-1;20  inc(tot); exit(tot-1);21 end;22 23 procedure insert(s:string);24 var c,i,v:longint;25 begin26  v:=root;27  for i:= 1 to length(s) do28   begin29    c:=ord(s[i])-65;30    if next[v,c]=-1 then next[v,c]:=new;31    v:=next[v,c];32   end;33  pd[v]:=true;34 end;35 36 procedure build;37 var v,tmp,i:longint;38 begin39  f[root]:=root;40  head:=1; tail:=0;41  for i:= 0 to maxs do42   if next[root,i]<>-1 then43     begin f[next[root,i]]:=root; push(next[root,i]); end;44  while head<=tail do45   begin46    v:=q[head]; inc(head);47    for i:= 0 to maxs do48     if next[v,i]<>-1 then49      begin50       push(next[v,i]);51       tmp:=f[v];52       while (tmp<>root) and (next[tmp,i]=-1) do tmp:=f[tmp];53       if next[tmp,i]<>-1 then tmp:=next[tmp,i];54       if tmp=-1 then f[next[v,i]]:=root else f[next[v,i]]:=tmp;55       if not pd[next[v,i]] then pd[next[v,i]]:=pd[tmp];56      end;57   end;58 end;59 60 procedure solve;61 var i,j,k,v,cnt,ans:longint;62 begin63  dp[0,0]:=1;64  for i:= 1 to m do65   for j:= root to tot do66    if (not pd[j]) and (dp[j,i-1]>0) then67     for k:= 0 to maxs do68      begin69       v:=j;70       while (next[v,k]=-1) and (v<>root) do v:=f[v];71       if next[v,k]<>-1 then v:=next[v,k];72       if not pd[v] then dp[v,i]:=(dp[v,i]+dp[j,i-1]) mod vv;73      end;74  cnt:=0;75  for i:= 0 to tot do cnt:=(cnt+dp[i,m]) mod vv;76  ans:=1;77  for i:= 1 to m do ans:=(ans*26) mod vv;78  ans:=(((ans-cnt) mod vv+vv) mod vv);79  writeln(ans);80 end;81 82 procedure init;83 var i:longint;84 begin85  readln(n,m);86  root:=new;87  for i:= 1 to n do88   begin89    readln(s);90    insert(s);91   end;92  build;93 end;94 95 Begin96  init;97  solve98 End.