#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=;

const int mod=;

struct Trie{

    int ok;

    int fail;

    int next[];

    void Init(){

        ok=;

        fail=-;

        memset(next,-,sizeof(next));

    }

}a[N];

char wrd[];

char str[N];

int n,m,cnt,q[N];

int find(char ch){

    switch(ch){

        case 'A':return ;

        case 'C':return ;

        case 'T':return ;

        case 'G':return ;

    }

    return ;

}

void InsertTrie(char *str){

    int p=;

    for(int i=;str[i]!='\0';i++){

        int id=find(str[i]);

        if(a[p].ok)

            break;

        if(a[p].next[id]==-){

            a[p].next[id]=cnt++;

            a[cnt-].Init();

        }

        p=a[p].next[id];

    }

    a[p].ok++;

}

void AC_automation(){

    int head=,tail=;

    q[tail++]=;

    int cur=,tmp;

    while(head<tail){

        cur=q[head++];

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

            tmp=a[cur].next[i];

            if(tmp!=-){

                if(cur==)

                    a[tmp].fail=;

                else{

                    a[tmp].fail=a[a[cur].fail].next[i];

                    if(a[a[tmp].fail].ok)

                        a[tmp].ok++;

                }

                q[tail++]=a[cur].next[i];

            }else{

                if(cur==)

                    a[cur].next[i]=;

                else

                    a[cur].next[i]=a[a[cur].fail].next[i];

            }

        }

    }

}

struct Matrix{

    long long m[][];

};

Matrix init,unit;

void Init(){

    memset(init.m,,sizeof(init.m));

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

        if(!a[i].ok)

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

                if(a[a[i].next[j]].ok==)

                    init.m[i][a[i].next[j]]++;

            }

                //if(a[*a[i].next[j]].ok==0)

                    //init.m[i][*a[i].next[j]]++;

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

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

            unit.m[i][j]=(i==j)?:;

}

Matrix Mul(Matrix a,Matrix b){

    Matrix c;

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

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

            c.m[i][j]=;

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

                c.m[i][j]=(a.m[i][k]*b.m[k][j])%mod;

            c.m[i][j]%=mod;

        }

    return c;

}

Matrix Pow(Matrix a,Matrix b,int k){

    while(k){

        if(k&){

            b=Mul(a,b);

        }

        a=Mul(a,a);

        k>>=;

    }

    return b;

}

int main(){

    freopen("input.txt","r",stdin);

    while(~scanf("%d%d",&n,&m)){

        cnt=;

        a[].Init();

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

            scanf("%s",wrd);

            InsertTrie(wrd);

        }

        AC_automation();

        Init();

        Matrix res=Pow(init,unit,m);

        long long ans=;

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

            if(a[i].ok==)

                ans=(ans+res.m[][i])%mod;

        cout<<ans<<endl;

    }

    return ;

}