#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 1100005
#define mod 19930726
#define ll long long
#define int ll
using namespace std;
char s[N<<1],a[N<<1];
int p[N],n,le,k,cnt[N],ans=1,tot;
void read(){
	scanf("%s",a+1);
	//n=strlen(a);
    s[0]='~',s[1]='#';
    for(int i=1;i<=le;i++)s[i*2-1]='#',s[i*2]=a[i];
	le=le*2+1,s[le]='#';
}
void mnc(){
	read();
	int maxr=0,mid=0;
	for(int i=1;i<=le;i++){
		if(i<maxr)p[i]=min(maxr-i,p[mid*2-i]);
		else p[i]=1;
		for(;s[p[i]+i]==s[i-p[i]];++p[i]);
		if(p[i]+i>maxr)maxr=p[i]+i,mid=i;
		if((p[i]-1)%2)cnt[p[i]-1]++;
	}
}
ll qpow(int x,int y){
	if(x==1)return 1;
    ll ans=1;
    while(y) {
        if(y&1)ans=(ans*x)%mod;
        x=(x*x)%mod;
        y>>=1;
    }
    return ans;
}
signed main(){
    scanf("%lld%lld",&n,&k);
	le=n;
    mnc();
    for(int i=n;i>=1;i--){
    	if(!(i&1))continue;
    	tot+=cnt[i];
    	if(k<=tot){
    		ans=(ans*qpow(i,k))%mod;
			k-=tot;
			break;
		}
		else{
			ans=(ans*qpow(i,tot))%mod;
			k-=tot;
		}
	}
    if(k>0)printf("%lld",ans-1);
    else printf("%lld",ans);
    return 0;
}