Description
艾利斯頓商學院籃球隊要參加一年一度的市籃球比賽了。拉拉隊是籃球比賽的一個看點，好的拉拉隊往往能幫助球隊增加士氣，赢得最終的比賽。是以作為拉拉隊隊長的楚雨荨同學知道，幫助籃球隊訓練好拉拉隊有多麼的重要。拉拉隊的選拔工作已經結束，在雨荨和校長的挑選下，n位集優秀的身材、舞技于一體的美女從衆多報名的女生中脫穎而出。這些女生将随着籃球隊的小夥子們一起，和對手抗衡，為艾利斯頓籃球隊加油助威。一個陽光明媚的早晨，雨荨帶領拉拉隊的隊員們開始了排練。n個女生從左到右排成一行，每個人手中都舉了一個寫有26個小寫字母中的某一個的牌子，在比賽的時候揮舞，為小夥子們呐喊、加油。雨荨發現，如果連續的一段女生，有奇數個，并且他們手中的牌子所寫的字母，從左到右和從右到左讀起來一樣，那麼這一段女生就被稱作和諧小群體。現在雨荨想找出所有和諧小群體，并且按照女生的個數降序排序之後，前K個和諧小群體的女生個數的乘積是多少。由于答案可能很大，雨荨隻要你告訴她，答案除以19930726的餘數是多少就行了。
Input
輸入為标準輸入。第一行為兩個正整數n和K，代表的東西在題目描述中已經叙述。接下來一行為n個字元，代表從左到右女生拿的牌子上寫的字母。
Output
輸出為标準輸出。輸出一個整數，代表題目描述中所寫的乘積除以19930726的餘數，如果總的和諧小群體個數小于K，輸出一個整數-1。
Sample Input
5 3
ababa Sample Output
45
【樣例說明】
和諧小群體女生所拿牌子上寫的字母從左到右按照女生個數降序排序後為ababa, aba, aba, bab, a, a, a, b, b，前三個長度的乘積為。
Hint
總共20個測試點，資料範圍滿足：
#pragma comment(linker, "/STACK:102400000,102400000")
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<functional>
using namespace std;
typedef long long LL;
const int low(int x) { return x&-x; }
const int INF = 0x7FFFFFFF;
const int mod = 19930726;
const int maxn = 1e6 + 10;
int n;
LL m;
char s[maxn];
struct PalindromicTree
{
const static int maxn = 1e6 + 10;
const static int size = 26;
int next[maxn][size], sz, tot;
int fail[maxn], len[maxn], last;
LL cnt[maxn], c[maxn];
char s[maxn];
void clear()
{
len[1] = -1; len[2] = 0;
fail[1] = fail[2] = 1;
last = (sz = 3) - 1; tot = 0;
memset(next[1], 0, sizeof(next[1]));
memset(next[2], 0, sizeof(next[2]));
}
int Node(int length)
{
memset(next[sz], 0, sizeof(next[sz]));
len[sz] = length; cnt[sz] = 0; return sz++;
}
int getfail(int x)
{
while (s[tot] != s[tot - len[x] - 1]) x = fail[x];
return x;
}
int add(char pos)
{
int x = (s[++tot] = pos) - 'a', y = getfail(last);
if (next[y][x]) { last = next[y][x]; }
else {
last = next[y][x] = Node(len[y] + 2);
fail[last] = len[last] == 1 ? 2 : next[getfail(fail[y])][x];
}
return ++cnt[last];
}
LL get(int x, LL y)
{
LL z = 1;
for (LL i = x; y; y >>= 1)
{
if (y & 1) z = z*i%mod;
i = i*i%mod;
}
return z;
}
void work()
{
LL ans = 1;
for (int i = 1; i <= tot; i++) c[i] = 0;
for (int i = sz-1; i > 2; i--)
{
cnt[fail[i]] += cnt[i];
if (len[i] & 1) c[len[i]] += cnt[i];
}
for (int i = tot; i&&m>0; i--)
{
ans = ans*get(i, min(c[i], m)) % mod;
m -= c[i];
}
if (m > 0) printf("-1\n"); else printf("%lld\n", ans);
}
}solve;
int main()
{
while (scanf("%d%lld%s", &n, &m, s) != EOF)
{
solve.clear();
for (int i = 0; s[i]; i++) solve.add(s[i]);
solve.work();
}
return 0;
}