记录编号	235593	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队 2011] 拉拉队排练	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	0.427 s
提交时间	2016-03-11 10:04:24	内存使用	127.22 MiB

#include<stdio.h>
#define MOD 19930726
#define ll long long
ll m;
ll ans=1;
ll POW(ll x,ll y){
	ll an=1;
	while(y){
		if(y&1) an=an*x%MOD;
		y>>=1,x=x*x%MOD;
	}
	return an;
}
int n,c[1100000];
char ch[1100000];
struct PAM{
	int cnt,last;
	int son[1100000][26],fa[1100000],l[1100000],s[1100000];
	PAM(){cnt=1,fa[0]=fa[1]=1,l[1]=-1;}
	void add(int c,int n){
		int p=last;
		while(ch[n-l[p]-1]!=ch[n]) p=fa[p];
		if(!son[p][c]){
			int now=++cnt,k=fa[p];
			l[now]=l[p]+2;
			while(ch[n-l[k]-1]!=ch[n]) k=fa[k];
			fa[now]=son[k][c],son[p][c]=now;
		}
		last=son[p][c],++s[last];
	}
	void sol(){
		for(int i=cnt;i;--i) s[fa[i]]+=s[i];
		for(int i=cnt;i;--i) c[l[i]]+=s[i];
		for(int i=n;i;--i)
		    if(i&1){
				if(m<=c[i]){
					ans=ans*POW(i,m)%MOD;
					break;
				}else ans=ans*POW(i,c[i])%MOD,m-=c[i];
		    }
		printf("%lld\n",ans);
	}
}pam;
int main(){
	freopen("rehearse.in","r",stdin);
	freopen("rehearse.out","w",stdout);
	scanf("%d%lld",&n,&m);
	scanf("%s",ch+1);
	for(int i=1;i<=n;++i) pam.add(ch[i]-97,i);
	pam.sol();
	//while(1);
}