记录编号	235477	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队 2011] 拉拉队排练	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	0.888 s
提交时间	2016-03-10 20:30:47	内存使用	163.37 MiB

#define maxa 26ul
#define maxn 10000010ul

#define ll long long

#include <stdio.h>
#include <algorithm>

struct pii{int x;ll y;}st[maxn];

int tot_state;

namespace PT{
	#define null NULL
	struct node{
		node *ch[maxa],*fail;
		int len,id;ll v;
		node(int id_,int len_){
			for(int i=0;i<maxa;i++) ch[i]=null;
			id=id_,len=len_,v=0;
			return;
		}
	}*now,*root[2],*pre[maxn];
	char s[maxn];
	int n,tot_n;
	void init(){
		tot_n=0;
		root[0]=new node(0,-1),pre[0]=root[0];
		root[1]=new node(++tot_n,0),pre[1]=root[1];
		root[0]->fail=root[1]->fail=root[0];
		now=root[1],n=0,s[n++]=-1;
		return;
	}
	node* get_node(int x){
		node *p=new node(++tot_n,x);
		pre[tot_n]=p;
		return p;
	}
	node* get_fail(node* p){
		while(s[n-p->len-2]!=s[n-1]) p=p->fail;
		return p;
	}
	void add(char c){
		int t=c-'a';s[n++]=c;
		node *p=get_fail(now);
		if(p->ch[t]==null){
			now=get_node(p->len+2);
			if(now->len==1) now->fail=root[1];
			else now->fail=get_fail(p->fail)->ch[t];
			p->ch[t]=now;
		}
		now=p->ch[t],now->v++;
		return;
	}
	void count(){
		for(int i=tot_n;i>=0;i--){
			node *tmp=pre[i];
			tmp->fail->v+=tmp->v;
			if((tmp->len&1)&&i>1){
				++tot_state;
				st[tot_state]=(pii){
					tmp->len,tmp->v
				};
			}
		}
		return;
	}
}

int n;ll K,ans=1,mod=19930726ll;
char str[maxn];

bool comp(const pii &a,const pii &b){
	return a.x>b.x;
}

ll ksm(ll p,ll k){
	ll res=1;
	while(k){
		if(k&1) (res*=p)%=mod;
		k>>=1,(p*=p)%=mod;
	}
	return res;
}

int main(){
	freopen("rehearse.in","r",stdin);
	freopen("rehearse.out","w",stdout);
	scanf("%d%lld%s",&n,&K,str);
	PT::init();
	for(int i=0;i<n;i++) PT::add(str[i]);
	PT::count();
	std::sort(st+1,st+tot_state+1,comp);
	for(int i=1;K&&i<=tot_state;i++){
		st[i].y=std::min(st[i].y,K);
		(ans*=ksm(st[i].x,st[i].y))%=mod;
		K-=st[i].y;
	}
	if(K) puts("-1");
	else printf("%lld",ans);
	return 0;
}