#include<cstdio>#include<cstring>#include<queue>using namespace std;const int mod = 100000;const int N = 20;const int M = 110;char s[N];typedef long long LL;int sz;struct Matrix{ LL x[M][M];};Matrix operator * (Matrix A, Matrix B){ Matrix C; for(int i=0; i<sz; i++){ for(int j=0; j<sz; j++){ LL &t = C.x[i][j]; t = 0; for(int k=0; k<sz; k++){ if(A.x[i][k] && B.x[k][j]){ t += A.x[i][k] * B.x[k][j]; } } t %= mod; } } return C; }Matrix pow(Matrix A, int p){ Matrix S; for(int i=0; i<sz; i++){ for(int j=0; j<sz; j++) S.x[i][j] = i==j?1:0; } while(p){ if(p&1) S = S*A; A = A*A; p>>=1; } return S;}struct ACAuto{ int ch[M][4], f[M]; bool mk[M]; void init(){ memset(ch[0], 0, sizeof(ch[0])); sz = 1; f[0] = mk[0] = 0; } int idx(char c){ switch(c){ case 'A':return 0; case 'G':return 1; case 'C':return 2; default: return 3; } } void insert(){ int len = strlen(s); int u = 0; for(int i=0; i<len; i++){ int c = idx(s[i]); if(!ch[u][c]){ memset(ch[sz],0,sizeof(ch[sz])); mk[sz] = 0; ch[u][c] = sz++; } u = ch[u][c]; } mk[u] = 1; } void getFail(){ queue<int> Q; for(int i=0; i<4; i++){ int u = ch[0][i]; if(u){ Q.push(u); f[u] = 0; } } while(!Q.empty()){ int r=Q.front(); Q.pop(); for(int c=0; c<4; c++){ int u = ch[r][c]; if(!u){ ch[r][c] = ch[f[r]][c]; continue; } Q.push(u); int v = f[r]; while(v && !ch[v][c]) v = f[v]; f[u] = ch[v][c]; mk[u] |= mk[f[u]]; } } } Matrix getMatrix(){ Matrix A; memset(A.x, 0, sizeof(A.x)); for(int i=0; i<sz; i++){ for(int j=0; j<4; j++){ int u = ch[i][j]; if(!mk[u]) A.x[i][u]++; } } return A; }}ac;int main(){ int n, m; while(~scanf("%d %d", &n, &m)){ ac.init(); while(n--){ scanf("%s", s); ac.insert(); } ac.getFail(); Matrix A = ac.getMatrix(); A = pow(A, m); int ans = 0; for(int i=0; i<sz; i++){ ans += A.x[0][i]; if(ans>=mod) ans-=mod; } printf("%dn", ans); } return 0;}
