1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
| #include <iostream>
#include <cstring>
#define maxn 1000010
#define ll long long
using namespace std;
const int p = 19930726;
ll pow_mod(ll x, ll n) {
ll s = 1;
for (; n; n >>= 1, x = x * x % p)
if (n & 1) s = s * x % p;
return s;
}
int n; ll k;
char s[maxn];
struct Manacher {
int n, l, f[maxn * 2], Len;
char s[maxn * 2];
void init(char *c) {
l = strlen(c + 1); s[0] = '~';
for (int i = 1, j = 2; i <= l; ++i, j += 2)
s[j] = c[i], s[j - 1] = '#';
n = 2 * l + 1; s[n] = '#'; s[n + 1] = '\0';
}
void manacher() {
int p = 0, mr = 0;
for (int i = 1; i <= n; ++i) {
if (i < mr) f[i] = min(f[2 * p - i], mr - i);
while (s[i + f[i]] == s[i - f[i]]) ++f[i]; --f[i];
if (f[i] + i > mr) mr = i + f[i], p = i;
Len = max(Len, f[i]);
}
}
ll d[maxn];
int solve() {
for (int i = 1; i <= n; ++i) {
int L = i - f[i] + 1 >> 1, R = i + f[i] - 1 >> 1, len = R - L + 1;
if (!f[i]) continue;
if (len & 1) ++d[1], --d[len + 2];
else ++d[2], --d[len + 2];
} int ans = 1; ll num = 0;
for (int i = 1; i <= l; ++i) {
if (i >= 2) d[i] += d[i - 2];
if (i & 1) num += d[i];
}
if (num < k) return -1; num = k;
for (int i = l - (~l & 1); i > 0; i -= 2) {
int t = min(num, d[i]); num -= t;
ans = ans * pow_mod(i, t) % p;
} return ans;
}
} M;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> k >> s + 1; M.init(s); M.manacher();
cout << M.solve() << "\n";
return 0;
}
|