记录编号	342534	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队 2011] 拉拉队排练	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	1.423 s
提交时间	2016-11-08 16:41:52	内存使用	104.24 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <list>
#include <vector>
#include <string>
#include <queue>
using namespace std;
typedef long long LL;
char str[1000033];
int len[1000033];
LL cnt[1000033];
int fail[1000033];
int next[1000004][26];
int tot, sum, last, slen;
typedef long long LL;
LL fast_read()
{
    LL r = 0;
    char c;
    bool sig = false;
    while(c = getchar())
    {
        if(c >= '0' && c <= '9')
        {
            r = c^0x30;
            break;
        }else if(c == '-')
            sig = true;
    }
    while(isdigit(c = getchar()))
        r = (r<<3)+(r<<1)+(c^0x30);
    if(sig)return -r;
    return r;
}
int read_string()
{
    int len = 2;
    char c;
    while(!isalpha(c = getchar()));
    str[1] = c-'a';
    while(isalpha(c = getchar()))
        str[len++] = c-'a';
    str[len] = 0;
    return len-1;
}
int find(int x)
{
    while(tot-len[x] == 1 || str[tot-len[x]-1] != str[tot])
        x = fail[x];
    return x;
}
bool cmp(int a, int b)  //澶?畫鏆翠簡闀垮害100W...涓嶆暍鍐欒?鏁版帓搴忎簡閮?.
{
    return len[a]>len[b];
}

#define MOD 19930726
LL fast_pow(LL base, LL exp)
{
    base %= MOD;
    LL ans = 1;
    while(exp)
    {
        if(exp & 1)ans = (ans*base)%MOD;
        exp >>= 1;
        base = (base*base)%MOD;
    }
    return ans;
}
int main()
{
    freopen("rehearse.in", "r", stdin);
    freopen("rehearse.out", "w", stdout);
    int n;
    LL k;
    n = (int)fast_read();
    k = fast_read();
    slen = read_string();
    sum = 1;
    len[0] = 0;
    len[1] = -1;
    fail[0] = 1;
    last = 1;
    for(int i = 1; i <= slen; i++)
    {
        tot = i;
        int c = find(last);
        if(!next[c][str[i]])
        {
            sum++;
            len[sum] = len[c]+2;
            fail[sum] = next[find(fail[c])][str[i]];
            next[c][str[i]] = sum;
        }
        last = next[c][str[i]];
        cnt[last]++;
    }
    LL ans = 1;
    for(int i = sum; i >= 2; i--)
        cnt[fail[i]] += cnt[i];
    priority_queue<pair<int, int> > q;
    for(int i = 2; i <= sum; i++)
        if(len[i]%2)q.push(make_pair(len[i], cnt[i]));
    while(k)
    {
        if(q.empty())
        {
            puts("-1");
            return 0;
        }
        if(k > q.top().second)
        {
            k -= q.top().second;
            ans = ans*fast_pow(q.top().first, q.top().second)%MOD;
            q.pop();
        }else
        {
            ans = ans*fast_pow(q.top().first, k)%MOD;
            k = 0;
        }
    }
    printf("%lld\n", ans);
    return 0;
}