#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LIM 201
#define mo 100000
#define MAX 10001
#define cp freopen
#define ll long long 
#define rep(i,a,b) for (int i=a;i<=b;i++)
using namespace std;
char S[MAX];
int s[MAX][4],d[MAX];  
int num=1,n,m,r[MAX],f[MAX]; 
vector<int> danger,pre[LIM]; 

struct trie
{
      int t[4]; 
}T[MAX]; 

struct mat
{
      int l1,l2;
      ll a[LIM][LIM];
      void print()
      {
            rep(i,1,l1)
            {
                  rep(j,1,l2)
                        cout<<a[i][j]<<' ';
                  cout<<endl; 
            }
            cout<<endl; 
      }
      void clear()
      {
            memset(a,0,sizeof(a)); 
      }
}; 

mat operator *(mat a,mat b)
{
      mat c;
      c.l1=a.l1,c.l2=b.l2;
      rep(i,1,a.l1)
            rep(j,1,b.l2)
            {
                  ll ans=0;
                  rep(k,1,a.l2)
                  {
                        ans+=a.a[i][k]*b.a[k][j];
                        ans%=mo;
                  }
                  c.a[i][j]=ans; 
            }
      return c; 
}

void ac_ins(int vi,int *r)
{
      int now=r[0]; 
      if (!T[vi].t[now])
            T[vi].t[now]=++num;
      if (r[1]==-1)
            danger.push_back(
                  T[vi].t[now]);
      else
            ac_ins(T[vi].t[now],r+1); 
}

void init()
{
      int c[500];
      c['A']=0;
      c['G']=1;
      c['C']=2;
      c['T']=3; 
      cin>>n>>m;
      gets(S); 
      rep(i,1,n)
      {
            gets(S); 
            int L=strlen(S);
            rep(i,0,L-1)
                  r[i]=c[S[i]];
            r[L]=-1; 
            ac_ins(1,r); 
      }
}

void ac_build()
{
      f[1]=1; 
      queue<int> Q;
      rep(i,0,3)
            if (T[1].t[i])
            {
                  Q.push(T[1].t[i]);
                  f[T[1].t[i]]=1; 
                  pre[1].push_back(T[1].t[i]); 
            }
      while (!Q.empty())
      {
            int h=Q.front(); 
            Q.pop();
            rep(i,0,3)
            {
                  if (!T[h].t[i])
                        continue; 
                  Q.push(T[h].t[i]);
                  int p=f[h];
                  while (p!=1&&!T[p].t[i])
                        p=f[p];
                  f[T[h].t[i]]=max(1,T[p].t[i]);
                  pre[max(1,T[p].t[i])].push_back(
                        T[h].t[i]);  
            }
      } 
}

int dfa(int vi,int j)
{
      if (T[vi].t[j])
            s[vi][j]=T[vi].t[j];
      if (s[vi][j]==-1&&vi==1)
            s[vi][j]=1; 
      if (s[vi][j]!=-1)
            return s[vi][j]; 
      s[vi][j]=dfa(f[vi],j);             
      return s[vi][j]; 
}

void ac_dfa()
{
      memset(s,-1,sizeof(s)); 
      rep(i,1,num)
            rep(j,0,3)
                  s[i][j]=dfa(i,j); 
}

void dfs(int vi)
{
 //     cout<<vi<<endl; 
      if (d[vi])
            return;
      d[vi]=1;
      rep(i,0,int(pre[vi].size()-1))
            dfs(pre[vi][i]); 
} 

void ac_danger()
{
      rep(i,0,int(danger.size()-1))
            dfs(danger[i]); 
}

void ac_calc()
{
      mat a,b;
      a.clear(); 
      b.clear();  
      a.l1=1,a.l2=num; 
      a.a[1][1]=1;
      b.l1=b.l2=num;
      rep(i,1,num)
      {
            if (d[i])
                  continue;
            rep(j,0,3)
            {
                  if (d[s[i][j]])
                        continue;
                  b.a[i][s[i][j]]++; 
            }
      }
    //  b.print(); 
      while (m)
      {
            if (m%2==1) 
                  a=a*b;
            b=b*b;
            m/=2; 
      }
      ll ans=0;
      rep(i,1,num)
            ans+=a.a[1][i],ans%=mo;
      cout<<ans<<endl; 
}

void solve()
{
      ac_build(); 
      ac_dfa(); 
      ac_danger(); 
      ac_calc();
}

void work()
{
      init();
      solve(); 
}

int main()
{
      cp("1.in","r",stdin); 
      cp("1.out","w",stdout); 
      
      work(); 
      
      return 0; 
}