#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10,mod=19930726;
long long n,k,maxn,p[N],ans=1;
map<long long,long long>	mp;
char a[N],s[N<<1];
void change(){
	s[0]='$';s[1]='#';
	long long w=2;
	for(long long i=1;i<=n;i++){
		s[w]=a[i];	w++;
		s[w]='#';	w++;
	}
	s[w]='&';	n=w;
}
void manacher(){
	long long R=0,C;
	for(long long i=1;i<n;i++){
		if(i<R)	p[i]=min(p[(C<<1)-i],p[C]+C-i);
		else	p[i]=1;
		while(s[i+p[i]]==s[i-p[i]])		p[i]++;
		if(p[i]+i>R){
			R=p[i]+i;
			C=i;
		}
		mp[p[i]-1]++;
		if((p[i]-1)%2)	maxn=max(maxn,p[i]-1);
	}
}
long long pw(long long a,long long b){
	long long res=1;
	while(b){
		if(b&1){
		    res=(res%mod*a%mod)%mod;
			res%=mod;
		}
		b=b>>1;
		a=((a%mod)*(a%mod))%mod;
	}
	return res%mod;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);	cout.tie(0);
	cin>>n>>k;
	cin>>(a+1);
	change();	manacher();
	while(k){
	    if(maxn<0){
	         cout<<-1<<endl;
	         return 0;
	    } 
		if(k<=mp[maxn]){
			ans=(ans%mod*pw(maxn,k)%mod)%mod;
			ans%=mod;
			cout<<ans<<endl;
			return 0;
		}else{
			ans=(ans%mod*pw(maxn,mp[maxn])%mod)%mod;
			ans%=mod;
			k-=mp[maxn];
			mp[maxn-2]+=mp[maxn];
			maxn-=2;
		}
	}
	return 0;
}