1 #include <iostream>  2 #include <cstdio>  3 #include <cstring>  4 #include <queue>  5   6 #define maxn 11000  7 #define SIG 26  8 #define N 50  9 using namespace std; 10  11 typedef unsigned long long  ull; 12  13 int n; 14 struct mat{ 15     ull a[2][2]; 16     mat operator *(mat x){ 17         mat c; 18         for(int i = 0 ;i< 2;i ++){ 19             for(int j = 0;j < 2;j++){ 20                 c.a[i][j] = 0; 21                 for(int k = 0; k < 2;k++){ 22                     c.a[i][j] +=a[i][k] * x.a[k][j]; 23                 } 24             } 25         } 26         return c; 27     } 28     ull get(long long k){ 29         mat ans,x;ans.a[0][0] = ans.a[1][1] = 1; 30         ans.a[0][1] = ans.a[1][0] = 0; 31         x.a[0][0] = 26,x.a[0][1] = 0; 32         x.a[1][1] = x.a[1][0] = 1; 33         while(k){ 34             if(k&1) ans = ans * x; 35             k>>=1; 36             x=x*x; 37         } 38         return ans.a[1][0]*(ull)26; 39     } 40 }fuck; 41 struct Mat{ 42     ull a[N][N]; 43     void zero(){ 44         memset(a,0,sizeof(a)); 45     } 46     Mat operator *(const Mat x){ 47         Mat c; 48         c.zero(); 49         for(int i = 0;i <= n;i ++ ){ 50             for(int j = 0;j <= n;j ++){ 51                 for(int k = 0;k <= n;k ++){ 52                     c.a[i][j] += a[i][k]*x.a[k][j]; 53                 } 54             } 55         } 56         return c; 57     } 58     void one(){ 59         zero(); 60         for(int i = 0;i <= n;i ++){ 61             a[i][i] = 1; 62         } 63     } 64     ull getsum(int k){ 65         ull ans = fuck.get(k); 66         ans = ans - a[0][n-1] + 1; 67         return ans; 68     } 69 }; 70  71 struct AC{ 72     int ch[maxn][SIG]; 73     int val[maxn]; 74     int f[maxn]; 75     int cnt; 76     void init(){ 77         memset(ch[0],0,sizeof(ch[0])); 78         val[0] = f[0] = 0; 79         cnt = 1; 80     } 81     int idx(char x){return x - ‘a‘;} 82  83     void insert(char *P){ 84         int m = strlen(P); 85         int r = 0; 86         for(int i = 0;i < m;i ++){ 87             int c = idx(P[i]); 88             if(!ch[r][c]){ 89                 memset(ch[cnt],0,sizeof(ch[cnt])); 90                 ch[r][c] = cnt; 91                 val[cnt] = f[cnt] = 0; 92                 cnt ++; 93             } 94             r = ch[r][c]; 95         } 96         val[r] = 1; 97     } 98     void getfail(){ 99         queue<int> q;100 101         for(int c = 0; c < SIG; c ++){102             int u = ch[0][c];103             if(u){q.push(u);f[u] = 0;}104         }105         while(!q.empty()){106             int r = q.front(); q.pop();107             for(int c = 0; c < SIG ;c ++){108                 int u = ch[r][c];109                 if(!u){ch[r][c] = ch[f[r]][c];continue;}110                 q.push(u);111                 int v = f[r];112                 while(v && ch[v][c]) v = f[v];113                 f[u] = ch[v][c];114                 val[u] |= val[f[u]];115             }116         }117     }118     void setMat(Mat &ini){119         ini.zero();120         n = cnt + 1;121         for(int i = 0;i < cnt ;i ++)if(!val[i]){122             for(int c = 0 ; c < SIG ;c ++){123                 int u = ch[i][c];124                 if(!val[u]){ini.a[i][u] += 1;}125             }126         }127         for( int i = 0;i <=cnt;i++)128             ini.a[i][cnt] = 1;129     }130 }ac;131 132 133 Mat qmul(Mat x,long long k){134     Mat ans; ans.one();135     while(k){136         if(k&1){ans = ans * x;}137         k >>= 1;138         x = x*x;139     }140     return ans;141 }142 void solve(int m,int l){143     ac.init();144     char str[105];145     for(int i = 0;i < m;i ++){146         scanf("%s",str);147         ac.insert(str);148     }149     ac.getfail();150     Mat ini;151     ac.setMat(ini);152     Mat ans = qmul(ini,(long long)l+1);153     cout<<ans.getsum(l)<<endl;154 }155 int main()156 {157     int m,l;158     while(scanf("%d%d",&m,&l)!=EOF){159         solve(m,l);160     }161     return 0;162 }163 /*164 2 3165 aa ab166 */