#include<cstdio>

#include<cstring>

typedef long long lint;

const lint MOD=100000;

const int N=105;

struct matrix

{

    lint w[N][N];

    matrix(){memset(w,0,sizeof(w));}

};

int n,m,cnt,head,tail,ans;

int tr[N][5],fail[N],q[N],map[300];

bool danger[N];char s[N];

inline void insert(char *c)

{

    int len=strlen(c+1),k=0;

    for(register int i=1;i<=len;i++)

    {

        int t=map[(int)c[i]];

        if(!tr[k][t])tr[k][t]=++cnt;

        k=tr[k][t];

    }

    danger[k]=1;

}

inline void build()

{

    for(register int i=0;i<4;i++)if(tr[0][i])q[tail++]=tr[0][i],fail[tr[0][i]]=0;

    while(head<tail)

    {

        int k=q[head++];

        for(register int i=0;i<4;i++)

        {

            if(!tr[k][i])tr[k][i]=tr[fail[k]][i];

            else

            {

                fail[tr[k][i]]=tr[fail[k]][i];

                danger[tr[k][i]]|=danger[fail[tr[k][i]]];

                q[tail++]=tr[k][i];

            }

        }

    }

}

inline matrix mul(matrix a,matrix b)

{

    matrix res;

    for(register int i=0;i<=cnt;i++)

        for(register int k=0;k<=cnt;k++)if(a.w[i][k])

            for(register int j=0;j<=cnt;j++)

            {

                lint temp=(lint)(a.w[i][k]*b.w[k][j]);

                res.w[i][j]=(res.w[i][j]+temp);

                if(res.w[i][j]>MOD)res.w[i][j]%=MOD;

            }

    return res;

}

inline matrix powmod(matrix a,int b)

{

    matrix res;for(register int i=0;i<=cnt;i++)res.w[i][i]=1;

    for(;b;b>>=1,a=mul(a,a))if(b&1)res=mul(res,a);

    return res;

}

int main()

{

    //freopen("input.in","r",stdin);

    map['A']=0;map['C']=1;map['G']=2;map['T']=3;

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

    for(register int i=1;i<=m;i++)

    {

        scanf("%s",s+1);insert(s);

    }

    build();matrix res;

    for(register int i=0;i<=cnt;i++)if(!danger[i])

    {

        for(register int j=0;j<4;j++)

            if(!danger[tr[i][j]])res.w[i][tr[i][j]]++;

    }

    res=powmod(res,n);

    for(register int i=0;i<=cnt;i++)

    {

        ans=ans+res.w[0][i];

        while(ans>MOD)ans-=MOD;

    }

    printf("%d",ans);

    return 0;

}