rt，复杂度 $O(n \log n)$ T 了两个点。

提交记录

#include <bits/stdc++.h>
#define _for(i, a, b)  for (int i = (a); i <= (b); i ++ )
#define _all(i, a, b)  for (int i = (a); i >= (b); i -- )
#define ll long long
using namespace std;
const int N = 1e6 + 5, P = 19930726;
int n, l = 1, r = - 1, j, lim, f[N]; char s[N]; ll k, sum, ans = 1, w[N];
inline void Mul(ll & x, ll y) { (x *= y) %= P; }
inline ll pw(ll a, int b) {
	ll res = 1;
	while (b) {
		if (b & 1)  Mul(res, a);
		Mul(a, a), b >>= 1;
	}
	return res;
}
int main() {
	ios :: sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n >> k;
	_for (i, 1, n)  cin >> s[i];
	_for (i, 1, n) {
		j = i > r ? 1 : min(f[l + r - i], r - i + 1);
		while (1 <= i - j && i + j <= n && s[i - j] == s[i + j])  j ++ ;
		f[i] = j -- ;
		if (i + j > r)  l = i - j, r = i + j;
	}
	_for (i, 1, n)  w[f[i]] ++ , sum += f[i], lim = max(lim, f[i]);
	_all (i, lim, 1)  w[i] += w[i + 1];
	_all (i, lim, 1)  w[i] += w[i + 1];
	if (k > sum) { cout << - 1 << "\n"; return 0; }
	l = 1, r = lim; int mid, pos = 0;
	while (l <= r) {
		mid = (l + r) >> 1;
		if (w[mid] - w[lim + 1] < k)  pos = mid, r = mid - 1;
		else  l = mid + 1;
	}
	_for (i, pos, lim)  Mul(ans, pw(i * 2 - 1, w[i] - w[i + 1])), k -= w[i] - w[i + 1];
	Mul(ans, pw(pos * 2 - 3, k)), cout << ans << "\n";
	return 0;
}