记录编号	378122	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队 2011] 拉拉队排练	最终得分	100
用户昵称	哒哒哒哒哒！	是否通过	通过
代码语言	C++	运行时间	0.354 s
提交时间	2017-03-03 06:30:03	内存使用	32.74 MiB

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
#define ll long long 
ll read(){
	ll x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
	return x*f;
}
const ll maxn=2000100;
const ll mod=19930726;
ll n,K,p[maxn],sum[maxn];
char s[maxn];
ll qk_pow(ll a,ll b){
	ll p=1;
	for(;b;b/=2,a=1ll*a*a%mod)if(b&1)p=1ll*p*a%mod;
	return p;
}
void manacher(){
	ll mx=0,id=0;
	for(ll i=1;i<=n;i++){
		p[i]=i<mx?min(mx-i,p[2*id-i]):1;
		while(s[p[i]+i]==s[i-p[i]]) p[i]++;
		if(i+p[i]>mx) mx=p[i]+i,id=i;
	}
	for(ll i=2;i<=n;i+=2) sum[p[i]-1]++;
	for(ll i=n;i>=1;i-=2) sum[i]+=sum[i+2];
	//for(ll i=n;i>=1;i-=2) sum[i]+=sum[i+2];
	//for(ll i=1;i<=n;i++) printf("%d ",sum[i] );puts("");
}
int main(){
	freopen("rehearse.in","r",stdin);freopen("rehearse.out","w",stdout);
	n=read(),K=read();
	scanf("%s",s+1);
	n=n*2+1;
	for(ll i=n;i>=1;i--)
		if(i&1) s[i]='#';
		else s[i]=s[i>>1];
	s[0]='$';
	manacher();
	//for(ll i=1;i<=n;i++) printf("%d ",sum[i]);puts("");
	ll ans=1,res=0;
	for(ll i=n;i>=1;i-=2){
		if(res+sum[i]>=K){
			ans=ans*qk_pow(i,K-res)%mod;
			res=K;
			break;
		}
		res+=sum[i];
		ans=ans*qk_pow(i,sum[i])%mod;
	}
	if(res==K)printf("%lld\n",ans);
	else printf("-1\n");
	fclose(stdin);fclose(stdout);
	return 0;
}