WA 15分

#include<bits/stdc++.h>
using namespace std;
#define PAIX 1000005
#define P 19930726
long long n,k;
string nod;
char s[PAIX*2]={};
long long p[PAIX*2]={},ans=0,cnt;
long long dic[2000005]={};
void qr()
{
	char c;
	s[0]='*';
	cnt=0;
	getline(cin,nod);
    c=getchar();
	while(c>='a'&&c<='z'){s[++cnt]=c;c=getchar();}
	while(c<'a'||c>'z')return;
}
long long mul=1,cal=0;
long long quick_pow(long long b,long long x)
{
	long long del=b,add=1;
	while(x>1)
	{
		if(x%2)
		{
			add*=b;
			add%=P;
			x--;
		}
		del*=del;
		del%=P;
		x/=2;
	}
	return del*add%P;
}
int main()
{
	cin>>n>>k;
	qr();
	for(long long t=1,mid=-1,r=-1;t<=cnt;t++)
	{
		if(t<=r)p[t]=min(r-t+1,p[2*mid-t]);
		while(s[t-p[t]]==s[t+p[t]])p[t]++;
		if(t+p[t]-1>r)
		{
			r=t+p[t]-1;
			mid=t;
		}
		dic[2*p[t]-1]++;
		if(ans<2*p[t]-1)ans=2*p[t]-1;
	}
	for(long long i=ans;i>=1;i-=2)
	{
		if(k<=0)break;
		cal+=dic[i];
		if(k>=cal)
		{
			k-=cal;
			mul*=quick_pow(i,cal);
			mul%=P;
		}
		else
		{
			mul*=quick_pow(i,k);
			mul%=P;
			k=0;
			break;
		}
	}
	if(k>0)cout<<"-1"<<endl;
	else cout<<mul%P<<endl;
	return 0;
}