#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 2000010
using namespace std;
typedef long long ll;
const int mod=19930726;
int len[MAXN],cnt[MAXN];
ll n,k,ans(1);
char a[MAXN],b[MAXN];
inline ll read(){
	ll x=0,f=1;  char ch=getchar();
	while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
	while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
ll fast(ll a,ll b){ll mul(1);for(;b;b>>=1,a=a*a%mod)if(b&1)mul=mul*a%mod;return mul;}
void init(){
	scanf("%s",a+1); b[0]='&';  
	for(int i=1;i<=n;++i)  b[i*2-1]='#',b[i*2]=a[i];
	b[n*2+1]='#';  b[n*2+2]='$';
	n=n*2+1;
}
void manacher(){
	int pos=0,mx=0;
	for(int i=1;i<=n;++i){
		len[i]=i<mx?min(len[pos*2-i],mx-i):0;
		while(b[i-len[i]]==b[i+len[i]])  len[i]++;
		if(i+len[i]>mx)  mx=i+len[i],pos=i;
	}
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	n=read();  k=read();  int flag=0;
	init();  manacher();
	for(int i=1;i<=n;++i)  if(!(i&1)) cnt[len[i]-1]++;
	for(int i=n;i>2;--i)  cnt[i-2]+=cnt[i];
	for(int i=n;i;--i)if(cnt[i]){
		if(k>cnt[i])  k-=cnt[i],ans=ans*fast(i,cnt[i])%mod;
		else {ans=ans*fast(i,k)%mod;flag=1;break;}
	}
	if(!flag)  printf("-1");
	else printf("%lld\n",ans);
	return 0;
}