#include<cstdio>

#include<algorithm>

#include<iostream>

#include<cstring>

#include<queue>

#include<cmath>

using namespace std;

typedef long long ll;

const int mod=1e5;

const int maxn=;///只有4个字母

const int N=1e3+;

struct ac{

    int trie[N][maxn],fail[N];

    int tot,root;

    bool end[N];

    ll res[N][N],ans[N][N],tmp[N][N];

    int newnode(){

        for(int i=;i<maxn;i++){

            trie[tot][i]=-;

        }

        end[tot++]=;

        return tot-;

    }

    void init(){

        tot=;

        root=newnode();

        memset(res,,sizeof(res));

        memset(ans,,sizeof(ans));

        memset(end,false,sizeof(end));

    }

    int getid(char c){

        if(c=='A')

            return ;

        if(c=='C')

            return ;

        if(c=='T')

            return ;

        if(c=='G')

            return ;

    }

    void insert(char *buf,int id){

        int now=root,len=strlen(buf);

        for(int i=;i<len;i++){

            int x=getid(buf[i]);

            if(trie[now][x]==-)

                trie[now][x]=newnode();

            now=trie[now][x];

        }

        end[now]=true;//它的路径字符串本身就是一个不良单词

    }

    void getfail(){

        queue<int>que;

        while(!que.empty())

            que.pop();

        fail[root]=root;

        for(int i=;i<maxn;i++)

            if(trie[root][i]==-)

                trie[root][i]=root;

            else{

                fail[trie[root][i]]=root;

                que.push(trie[root][i]);

            }

        while(!que.empty()){

            int now=que.front();

            que.pop();

            if(end[fail[now]])//它的路径字符串的后缀对应的结点（即fail[i]）是危险结点

                end[now]=true;

            for(int i=;i<maxn;i++){

                if(trie[now][i]!=-){

                    fail[trie[now][i]]=trie[fail[now]][i];

                    que.push(trie[now][i]);

                }

                else

                    trie[now][i]=trie[fail[now]][i];

            }

        }

    }

    void path(){

        for(int i=;i<tot;i++){

            for(int j=;j<maxn;j++)

                if(!end[i]&&!end[trie[i][j]]){

                //    cout<<i<<"!!"<<j<<endl;

                    res[i][trie[i][j]]++;

                }

        }

    }

    void mul(ll a[][N],ll b[][N]){

        for(int i=;i<tot;i++)

            for(int j=;j<tot;j++){

                tmp[i][j]=;

                for(int k=;k<tot;k++)

                    tmp[i][j]=(tmp[i][j]+a[i][k]*b[k][j])%mod;

            }

        for(int i=;i<tot;i++)

            for(int j=;j<tot;j++)

                a[i][j]=tmp[i][j];

    }

    ll solve(int n){

        for(int i=;i<tot;i++)

            ans[i][i]=;

        while(n){

            if(n&){

                mul(ans,res);

            }

            n>>=;

            mul(res,res);

        }

        ll ANS=;

        for(int i=;i<tot;i++)

            ANS=(ANS+ans[][i])%mod;

        return ANS;

    }

}AC;

char s[];

int main(){

    int m,n;

    scanf("%d%d",&m,&n);

    AC.init();

    for(int i=;i<=m;i++){

        scanf("%s",s);

        AC.insert(s,i);

    }

    AC.getfail();

    AC.path();

    printf("%lld\n",AC.solve(n));

    return ;

}