背单词，始终是复习英语的重要环节。在荒废了3年大学生涯后，Lele也终于要开始背单词了。 
一天，Lele在某本单词书上看到了一个根据词根来背单词的方法。比如"ab",放在单词前一般表示"相反，变坏，离去"等。

于是Lele想，如果背了N个词根，那这些词根到底会不会在单词里出现呢。更确切的描述是：长度不超过L，只由小写字母组成的，至少包含一个词根的单词，一共可能有多少个呢？这里就不考虑单词是否有实际意义。

比如一共有2个词根 aa 和 ab ，则可能存在104个长度不超过3的单词，分别为 
(2个) aa,ab, 
(26个)aaa,aab,aac...aaz, 
(26个)aba,abb,abc...abz, 
(25个)baa,caa,daa...zaa, 
(25个)bab,cab,dab...zab。

这个只是很小的情况。而对于其他复杂点的情况，Lele实在是数不出来了，现在就请你帮帮他。

 

本题目包含多组数据，请处理到文件结束。 
每组数据占两行。 
第一行有两个正整数N和L。(0<N<6,0<L<2^31) 
第二行有N个词根，每个词根仅由小写字母组成，长度不超过5。两个词根中间用一个空格分隔开。 

 

对于每组数据，请在一行里输出一共可能的单词数目。 
由于结果可能非常巨大，你只需要输出单词总数模2^64的值。 

 

 

 

#include<queue>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

inline int f(char u){

    return u-'a';

}

struct tree{

    int f;

    bool w;

    int t[];

}t[];

int n,m,num=;

struct MX{

    unsigned long long c[][];

};

char s[];

bool ma[],us[];

queue <int> q;

MX a,o;

inline bool dfs(int x){

    if (x==) return ;

    if (t[x].w) return ;

    if (us[x]) return ma[x];

    us[x]=;

    return ma[x]=dfs(t[x].f);

}

inline void in(){

    int p=,l,m=strlen(s);

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

        l=f(s[i]);

        if (!t[p].t[l]) t[p].t[l]=++num;

        p=t[p].t[l];

    }

    t[p].w=;

}

inline void mafa(){

    register int i;int k,p;

    q.push();t[].f=;

    while(!q.empty()){

        k=q.front();q.pop();

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

        if (t[k].t[i]){

            p=t[k].f;

            while((!t[p].t[i])&&p) p=t[p].f;

            t[t[k].t[i]].f=(k==p)?:t[p].t[i];

            q.push(t[k].t[i]);

        }

    }

}

inline MX cheng(MX x,MX y){

    register int i,j,k;

    MX z;

    for (i=;i<=num;i++)

    if (ma[i])

    for (j=;j<=num;j++)

    if (ma[j]){

        z.c[i][j]=;

        for (k=;k<=num;k++)

        if (ma[k])

        z.c[i][j]+=x.c[i][k]*y.c[k][j];

    }

    return z;

}

inline MX mi(MX x,int b){

    register int i,j;

    MX z=x;b--;

    while(b){

        if (b&) z=cheng(z,x);

        b>>=;

        x=cheng(x,x);

    }

    return z;

}

int main(){

    register int i,j;int u;

    unsigned long long ans;

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

        u=ans=;

        for (i=;i<=num;i++)

        for (j=;j<;j++) t[i].t[j]=;

        for (i=;i<=num;i++) ma[i]=us[i]=t[i].w=t[i].f=;

        num=;

        a.c[][]=;

        a.c[][]=a.c[][]=;

        ma[]=ma[]=;

        o=mi(a,m);

        ma[]=ma[]=;

        ans=o.c[][]+o.c[][];

        for (i=;i<=num;i++)

        for (j=;j<=num;j++)

        a.c[i][j]=;

        num=;

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

              scanf("%s",s);

            in();

        }

        mafa();

        for (i=;i<=num;i++)

        ma[i]=dfs(i);

        for (i=;i<=num;i++)

        if (ma[i])

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

            if (!t[i].t[j]){

                u=t[i].f;

                while(!t[u].t[j]&&u)u=t[u].f;

                u=t[u].t[j];

            }else u=t[i].t[j];

            a.c[i][u]++;

        }

        num++;

        ma[num]=;

        for (i=;i<=num;i++) a.c[i][num]=;

        o=mi(a,m);

        for (i=;i<=num;i++)

        if (ma[i])

        ans-=o.c[][i];

        for (i=;i<=num;i++)

        for (j=;j<=num;j++)

        a.c[i][j]=;

        printf("%llu\n",ans);

    }

}