#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=1000005;
const int MOD=19930726;
int n,k,len,r[MAXN],R,c,ans=1,opt,t[MAXN+1];
char s[MAXN];

inline int read()
{
	int w=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		w=(w<<1)+(w<<3)+(ch-48);
		ch=getchar();
	}
	return w*f;
}

int Pow(int a,int b)
{
	int res=1;
	for(;b;b>>=1)
	{
		if(b&1)
		{
			res=(res*a)%MOD;
		}
		a*=a;
	}
	return res;
}

signed main()
{
	n=read();k=read();
	scanf("%s",s);
	for(int i=n;i>=1;i--)
	{
		s[i]=s[i-1];
	}
	len=n;
	for(int i=1;i<=len;i++)
	{
		if(i<=R)
		{
			r[i]=min(r[2*c-i],R-i+1);
		}
		else r[i]=1;
		while(s[i+r[i]]==s[i-r[i]])
		{
			r[i]++;
		}
		if(r[i]+i-1>R)
		{
			R=r[i]+i-1;
			c=i;
		}
		r[i]=r[i]*2-1;
	}//manacher
	for(int i=1;i<=n;i++)
	{
		t[r[i]]++;
	}
	for(int i=MAXN;i>=1;i-=2)
	{
		if(t[i]<=k)
		{	
			//printf("%lld ",k);
			//printf("%lld %lld\n",i,t[i]);
			ans=(ans%MOD*Pow(i,t[i]))%MOD;
			t[i-2]+=t[i];
			k-=t[i];
		}
		else
		{
			ans=(ans%MOD*Pow(i,k))%MOD;
			//printf("%lld\n",i);
			k=0;
			break;
		}
	}
	if(k>0)
	{
		//printf("-1\n");
		return 0; 
	}
	printf("%lld",ans);
	return 0;
}