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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=1000005;
const LL mod=19930726;
int n;
LL k,ans=1,f[maxn];
struct Palindsome_Automaton {
int child[maxn][26];
int n,size,last,s[maxn],len[maxn],next[maxn];
LL cnt[maxn];
Palindsome_Automaton() {
size=-1;
newnode(0);
newnode(-1);
last=n=0;
s[0]=-1;
next[0]=next[1]=1;
}
int newnode(int v) {
int now=++size;
len[now]=v;
return now;
}
void insert(int data) {
s[++n]=data;
int p=last;
while(s[n-len[p]-1]!=s[n])p=next[p];
if(!child[p][data]) {
int now=newnode(len[p]+2),q=next[p];
while(s[n-len[q]-1]!=s[n])q=next[q];
next[now]=child[q][data];
child[p][data]=now;
}
last=child[p][data];
cnt[last]++;
}
void build(string s) {
for(auto x:s)insert(x-'a');
}
void count() {
for(int i=size; i>=0; i--)cnt[next[i]]=(cnt[next[i]]+cnt[i])%mod;
for(int i=2; i<=size; i++)f[len[i]]=(f[len[i]]+cnt[i])%mod;
}
} pam;
char s[maxn];
LL Quick_Pow(LL a,LL b) {
LL ans=1;
while(b) {
if(b&1)ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans;
}
int main() {
n=Get_Int();
k=Get_Int();
scanf("%s",s);
pam.build(s);
pam.count();
int len=strlen(s);
for(int i=len; i>=1&&k; i--) {
if(!(i&1))continue;
ans=ans*Quick_Pow(i,min(k,f[i]))%mod;
k-=min(f[i],k);
}
if(k)puts("-1");
else printf("%lld\n",ans);
return 0;
}
|
