#include<bits/stdc++.h>
using namespace std;

const int nmax=10,mod=1e9+7;

int n,k;

long long adj[nmax][nmax];

long long help[nmax][nmax];

long long paths[nmax][nmax];

void mult_adj()
{
    memset(help,0,sizeof(help));

    for(int i=0;i<nmax;i++)
        for(int j=0;j<nmax;j++)
            for(int p=0;p<nmax;p++)
                help[i][j]=(help[i][j]+adj[i][p]*adj[p][j])%mod;

    for(int i=0;i<nmax;i++)
        for(int j=0;j<nmax;j++)
            adj[i][j]=help[i][j];
}

void mult_paths()
{
    memset(help,0,sizeof(help));

    for(int i=0;i<nmax;i++)
        for(int j=0;j<nmax;j++)
            for(int p=0;p<nmax;p++)
                help[i][j]=(help[i][j]+paths[i][p]*adj[p][j])%mod;

    for(int i=0;i<nmax;i++)
        for(int j=0;j<nmax;j++)
            paths[i][j]=help[i][j];
}

int inp[nmax];

char in()
{
    char c='?';

    while('a'>c||c>'j')c=getchar();

    return c-'a';
}

int main()
{

    freopen("words.in","r",stdin);
    freopen("words.out","w",stdout);

    scanf("%i%i",&n,&k);

    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<5;j++)inp[j]=in();

        adj[inp[0]][inp[4]]++;
    }

    for(int i=0;i<nmax;i++)
        paths[i][i]=1;

    while(k)
    {
        if(k%2)mult_paths();

        k=k/2;

        mult_adj();
    }

    long long outp=0;

    for(int i=0;i<nmax;i++)
        for(int j=0;j<nmax;j++)
            outp=(outp+paths[i][j])%mod;

    printf("%lld\n",outp);

    return 0;
}