艾利斯顿商学院篮球队要参加一年一度的市篮球比赛了。拉拉队是篮球比赛的一个看点，好的拉拉队往往能帮助球队增加士气，赢得最终的比赛。所以作为拉拉队队长的楚雨荨同学知道，帮助篮球队训练好拉拉队有多么的重要。拉拉队的选拔工作已经结束，在雨荨和校长的挑选下，n位集优秀的身材、舞技于一体的美女从众多报名的女生中脱颖而出。这些女生将随着篮球队的小伙子们一起，和对手抗衡，为艾利斯顿篮球队加油助威。一个阳光明媚的早晨，雨荨带领拉拉队的队员们开始了排练。n个女生从左到右排成一行，每个人手中都举了一个写有26个小写字母中的某一个的牌子，在比赛的时候挥舞，为小伙子们呐喊、加油。雨荨发现，如果连续的一段女生，有奇数个，并且他们手中的牌子所写的字母，从左到右和从右到左读起来一样，那么这一段女生就被称作和谐小群体。现在雨荨想找出所有和谐小群体，并且按照女生的个数降序排序之后，前K个和谐小群体的女生个数的乘积是多少。由于答案可能很大，雨荨只要你告诉她，答案除以19930726的余数是多少就行了。

输入为标准输入。第一行为两个正整数n和K，代表的东西在题目描述中已经叙述。接下来一行为n个字符，代表从左到右女生拿的牌子上写的字母。

输出为标准输出。输出一个整数，代表题目描述中所写的乘积除以19930726的余数，如果总的和谐小群体个数小于K，输出一个整数-1。

 1 //It is made by wfj_2048~ 2 #include <algorithm> 3 #include <iostream> 4 #include <complex> 5 #include <cstring> 6 #include <cstdlib> 7 #include <cstdio> 8 #include <vector> 9 #include <cmath>10 #include <queue>11 #include <stack>12 #include <map>13 #include <set>14 #define rhl (19930726)15 #define N (1000010)16 #define il inline17 #define RG register18 #define ll long long19 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)20 21 using namespace std;22 23 int ch[N][26],len[N],fail[N],st[N],n,la,sz,cnt;24 ll val[N],k,res,ans;25 char s[N];26 27 il ll gi(){28     RG ll x=0,q=1; RG char ch=getchar();29     while ((ch<‘0‘ || ch>‘9‘) && ch!=‘-‘) ch=getchar();30     if (ch==‘-‘) q=-1,ch=getchar();31     while (ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-48,ch=getchar();32     return q*x;33 }34 35 il int cmp(const int &a,const int &b){ return len[a]>len[b]; }36 37 il ll qpow(RG ll a,RG ll b){38     RG ll ans=1;39     while (b){40     if (b&1) ans=ans*a%rhl;41     a=a*a%rhl,b>>=1;42     }43     return ans;44 }45 46 il void insert(RG int c,RG int n){47     RG int x=la; while (s[n-len[x]-1]!=s[n]) x=fail[x];48     if (!ch[x][c]){49     RG int v=++sz,k=fail[x]; len[v]=len[x]+2;50     while (s[n-len[k]-1]!=s[n]) k=fail[k];51     fail[v]=ch[k][c],ch[x][c]=v;52     }53     la=ch[x][c],++val[ch[x][c]]; return;54 }55 56 il void work(){57     n=gi(),k=gi(),scanf("%s",s+1),len[++sz]=-1,fail[0]=1;58     for (RG int i=1;i<=n;++i) insert(s[i]-97,i);59     for (RG int i=sz;i>1;--i) val[fail[i]]+=val[i];60     for (RG int i=2;i<=sz;++i) if (len[i]&1) st[++cnt]=i,res+=val[i];61     if (res<k){ puts("-1"); return; } res=0,ans=1,sort(st+1,st+cnt+1,cmp);62     for (RG int i=1;i<=cnt;++i)63     if (res+val[st[i]]>=k){ ans=ans*qpow(len[st[i]],k-res)%rhl; break; }64     else res+=val[st[i]],ans=ans*qpow(len[st[i]],val[st[i]])%rhl;65     printf("%lld\n",ans); return;66 }67 68 int main(){69     File("team");70     work();71     return 0;72 }