记录编号	161960	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队 2011] 拉拉队排练	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	2.402 s
提交时间	2015-05-12 17:20:14	内存使用	171.97 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

#define N 10000010
#define A 26
#define LL long long
#define MP(x,y) make_pair(x,y)
#define mod 19930726LL
#define fir first
#define sec second
#define debug(x) cout<<#x<<" = "<<x<<endl;

using namespace std;

void file(){
	freopen("rehearse.in","r",stdin);
	freopen("rehearse.out","w",stdout);
}

pair<int,LL> ST[N];
int tot_S,ni;
LL K;

namespace PT{
	struct node{
		node *ch[A],*fail;
		int len,id;
		LL v;
	}*now,*root[2],*pre[N];
	
	char S[N];
	int n,tot,tot_n;
	
	void init(){
		root[0]=new node(); root[1]=new node();
		tot_n=0;
		root[0]->id=tot_n; pre[0]=root[0];
		root[1]->id=++tot_n; pre[1]=root[1];
		now=root[1];
		root[0]->fail=root[1]->fail=root[0];
		root[0]->len=-1; root[1]->len=0;
		n=0; tot=0;
		S[n++]=-1;
	}
	
	node* get_node(int x){
		node* tmp=new node();
		tmp->id=++tot_n;
		pre[tot_n]=tmp;
		tmp->len=x;
		return tmp;
	}
	
	node* get(node* p){
		while(S[n-p->len-2]!=S[n-1])
			p=p->fail;
		return p;
	}
	
	bool add(char c){
		int t=c-'a'; S[n++]=c;
		node* p=get(now);
		if(!p->ch[t]){
			now=get_node(p->len+2);
			if(now->len==1) now->fail=root[1];
			else now->fail=get(p->fail)->ch[t];
			p->ch[t]=now;
			tot++;
		}
		now=p->ch[t];
		now->v++;
		return 0;
	}
	
	void count(){
		tot_S=0;
		for(int i=tot_n;i>=0;i--){
			node* tmp=pre[i];
			tmp->fail->v+=tmp->v;
			if(tmp->len%2 && i>1)
				ST[++tot_S]=MP(-tmp->len,tmp->v);
		}
	}
};

char S[N];

LL qpow(LL x,LL n){
	LL ans=1;
	for(;n;n>>=1,x=x*x%mod)
		if(n&1) ans=ans*x%mod;
	return ans;
}

int main(){
	file();
	scanf("%d%lld",&ni,&K);
	scanf("%s",S);
	LL ans=1;
	PT::init();
	for(int i=0;i<ni;i++) PT::add(S[i]);
	PT::count();
	sort(ST+1,ST+tot_S+1);
	for(int i=1;K&&i<=tot_S;i++){
		ST[i].sec=min(ST[i].sec,K);
	//	debug(ST[i].sec);
	//	debug(ST[i].fir);
	//	debug(K);
		ans=ans*qpow(-ST[i].fir,ST[i].sec)%mod;
		K-=ST[i].sec;
	}
	if(K) printf("-1\n");
	else printf("%lld\n",ans);
	fclose(stdin);
	fclose(stdout);
	return 0;
}