> #include<stdio.h>
> struct node
> {
> 	struct node *next[5];
> 	struct node *fail;
> 	int flag,num;
> }*root,*line[3000];
> int m,n,i,j,nu,head,tail,key,k;
> long long anss;
> char str[20];
> struct M
> {
> 	long long x[300][300];
> }*mat,*ans;
> int getnum(char c)
> {
> 	if (c=='A') return 1;
> 	if (c=='C') return 2;
> 	if (c=='G') return 3;
> 	if (c=='T') return 4;
> }
> void trie()
> {
> 	struct node *p=root;
> 	int i=1;  int key;
> 	while (i<=strlen(str))
> 	{
> 		key=getnum(str[i-1]);
> 		if (p->next[key]==NULL)
> 		{
> 			p->next[key]=(struct node *)malloc(sizeof(struct node));
> 			nu++;
> 			p->next[key]->num=nu;
> 			for (j=1;j<=4;j++)
> 			{
> 				p->next[key]->next[j]=NULL;
> 			}
> 			p->next[key]->flag=0;
> 		}
> 		p=p->next[key];
> 		i++;
> 	}
> 	p->flag=1;
> }
> void buildac()
> {
> 	root->fail=NULL;
> 	line[1]=root;
> 	head=0; tail=1;
> 	while (head<tail)
> 	{
>         head++;
> 		struct node *p=line[head];
> 		for (i=1;i<=4;i++)
> 		{
> 			if (p->next[i]!=NULL)
> 			{
> 				if (p==root) p->next[i]->fail=root;
> 				else 
> 				{
> 					struct node *temp=p->fail;
> 					while (temp!=NULL)
> 					{
> 						if (temp->next[i]!=NULL) 
> 						{
> 							p->next[i]->fail=temp->next[i];
> 							break;
> 						}
> 						temp=temp->fail;
> 					}
> 					if (temp==NULL) p->next[i]->fail=root;
> 				}
> 				tail++;
> 				line[tail]=p->next[i];
> 			}
> 		}
> 	}
> }
> void buildmat()
> {
> 	struct node *p=root;
> 	line[head]=root;
> 	head=0;tail=1;
> 	int i;
> 	while (head<tail)
> 	{
> 		head++;
> 		p=line[head];
> 		if (p!=NULL && p->flag==0)
> 		{
> 			key=p->num;
> 			for (i=1;i<=4;i++)
> 			{
> 				if (p->next[i]!=NULL && p->next[i]->flag==0)
> 					mat->x[key][p->next[i]->num]++;
> 				if (p->next[i]==NULL) mat->x[key][1]++;
> 				if (p->next[i]!=NULL)
> 				{
>                                      tail++;
>                                      line[tail]=p->next[i];
>                 }
> 			}
> 		}
> 	}
> }
> struct M *mul(struct M *a, struct M *b)
> {
> 	struct M *c;
> 	c=(struct M *)malloc(sizeof(struct M));
> 	for (i=1;i<=nu;i++)
> 	{
> 		for (j=1;j<=nu;j++)
> 		{
> 			c->x[i][j]=0;
> 			for (k=1;k<=nu;k++)
> 			{
> 				c->x[i][j]+=(a->x[i][k])*(b->x[k][j]);
> 			}
> 		}
> 	}
> 	return c;
> }
> struct M *mi(struct M *a,int n)
> {
> 	struct M *ans;
> 	ans=(struct M *)malloc(sizeof(struct M));
> 	for (i=1;i<=nu;i++)
> 		ans->x[i][i]=1;
> 	while (n)
> 	{
> 		if (n&1) ans=mul(a,ans);
> 		a=mul(a,a);
> 		n=n>>1;
> 	}
> 	return ans;
> }
> int main()
> {
> 	scanf("%d%d",&m,&n);
> 	root=(struct node *)malloc(sizeof(struct node));
> 	for (i=1;i<=4;i++)
> 	{
> 		root->next[i]=NULL;
> 	}
> 	root->flag=0;
> 	root->num=1;
> 	nu=1;
> 	for (i=1;i<=m;i++)
> 	{
> 		scanf("%s",str);
> 		trie();
> 	}
> 	buildac();
> 	mat=(struct M *)malloc(sizeof(struct M));
> 	buildmat();
> 	mat=mi(mat,n);
> 	for (i=1;i<=nu;i++)
> 	{
> 		anss+=mat->x[1][i];
> 	}
> 	printf("%lld\n",(anss%100000));
> //	system("pause");
> 	return 0;
> }