记录编号	589695	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	游戏	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.156 s
提交时间	2024-07-07 13:08:48	内存使用	8.79 MiB

#include <bits/stdc++.h> 
using namespace std;
#define ll long long
#define pii pair<int,int>
const int N = 2e6+10;
const ll inf = 1e17,mod = 19930726;

ll read(){
    ll x = 0,f = 1;char c = getchar();
    for(;c < '0' || c > '9';c = getchar())if(c == '-')f = -1;
    for(;c >= '0' && c <= '9';c = getchar())x = (x<<1) + (x<<3) + c-'0';
    return x * f;
}


ll n,k,tmp[N],ans = 1,s;
string ch;
ll ksm(ll x,ll y){
    ll ans = 1;
    while(y){
        if(y & 1)ans = ans * x % mod;
        x = x * x % mod,y >>= 1;
    }return ans;
}
string reset(string &ch){
    string tmp = "#";int l = ch.length();
    for(int i = 0;i < ch.length();i++)tmp = tmp + ch[i] + "#";
    return tmp;
}
int r[N];
void manacher(){
    int len = ch.length(),c = 0;
    tmp[1]++;tmp[2]--;r[0] = 1;
    for(int i = 1;i < len;i++){
        if(i < c + r[c])r[i] = min(r[2 * c - i],c + c[r] - i);
        while(i - r[i] >= 0 && r[i] + i < len && ch[i - r[i]] == ch[i + r[i]])++r[i];
        --r[i];
        if(i + r[i] > c + r[c])c = i;
        tmp[1]++,tmp[2 * r[i] + 2]--;
    } 
    for(int i = 2;i <= len;i++)tmp[i] += tmp[i-1];
}
int main(){
    freopen("rehearse.in","r",stdin);
    freopen("rehearse.out","w",stdout);
    n = read(),k = read();
    cin>>ch;
//    ch = reset(ch);
    manacher();
    s = n % 2 == 1 ? n : n-1;
    for(;s >= 1;s -= 2){
        if(k){
            ll u = min(k,tmp[s]);k -= u;
            ans = ans * ksm(s,u) % mod;
        }
    }
    if(k != 0)printf("-1\n");
    else printf("%lld\n",ans);
    
    return 0;
    
}