我的做法是manacher后计算答案。

但由于我太菜了，式子里有个 $a \times (a+2) \times (a+4) \times ... \times b$，本想搞个分块的，先交了发暴力计算这个式子，结果过了，理论复杂度不是 $O(n^2)$ 的吗？

#include<bits/stdc++.h>
#define int long long
#define mod 19930726
#define N 3000007
#define siz 1000
using namespace std;
int n, k, cnt, ans = 1;
int p[N], b[N], fac[N], Inv[N]; //预处理双阶乘 
char a[N], s[N];
int Pow(int a, int n) {
	if(n == 0) return 1;
	if(n == 1) return a;
	int x = Pow(a, n / 2);
	if(n % 2 == 0) return x * x % mod;
	else return x * x % mod * a % mod;
} 
int inv(int x) {
	return Pow(x, mod - 2);
}
bool cmp(int x, int y) {
	return x > y;
}
void manacher() {
	s[++cnt] = '$';
	for(int i = 1; i <= n; i++) s[++cnt] = a[i];
	s[++cnt] = '~';
	int mid = 0, mr = 0;
	for(int i = 2; i <= cnt - 1; i++) {
		if(i <= mr) p[i] = min(mr - i + 1, p[mid * 2 - i]);
		else p[i] = 1;
		while(s[i - p[i]] == s[i + p[i]]) p[i]++;
		if(i + p[i] - 1 > mr) mid = i, mr = i + p[i] - 1;
		b[i - 1] = 2 * p[i] - 1;
	}
	sort(b + 1, b + n + 1, cmp);
}
int Get(int L, int R) { //暴力计算这个式子 
	int res = 1;
	for(int i = L; i <= R; i += 2) res = res * i % mod;
	return res;
}
int work() {
	fac[1] = 1;
	for(int i = 3; i <= n; i += 2) fac[i] = fac[i - 2] * i % mod;
	b[n + 1] = -1;
	for(int i = 1; i <= n; i++) {
		int use = (b[i] - b[i + 1]) / 2 * i;
		if(k >= use) {
			k -= use;
			if(b[i + 1] != -1) ans = ans * Pow(Get(b[i + 1] + 2, b[i]), i) % mod;
			else ans = ans * Pow(fac[b[i]], i) % mod;
			if(k == 0) return ans;
		}
		else {
			int z = k / i; //砍的轮数
			k -= z * k;
			ans = ans * Pow(Get(b[i] - 2 * z + 2, b[i]), i) % mod;
			ans = ans * Pow(b[i] - 2 * z, k) % mod;
			return ans;
		}
	}
	return -1;
}
signed main() {
    scanf("%lld %lld", &n, &k);
    scanf("%s", a + 1);
    manacher();
    //init();
    printf("%lld", work());
	return 0;
}