可以用数据结构维护，如线段树等，也可以差分

因此应当添加算法标签

#include<bits/stdc++.h>
#define int long long
#define maxn 4000010
using namespace std;
int n,tot,r,p,ans=1;const int mod=19930726;
char a[maxn],s[maxn];
int dp[maxn],k;
int maxr[maxn],cf[maxn],base,cnt[maxn];
int h[maxn],maxccf;
priority_queue<int>q; 
inline int ksm(int d,int z){
	int res=1;
	while(z){
		if(z&1)res=(res*d)%mod;
		d=(d*d)%mod;z>>=1; 
	}
	return res;
}
signed main(){
	cin>>n>>k;
	for(int i=1;i<=n;++i)cin>>a[i];
	s[++tot]='@';s[0]=s[tot+1]='@';
	for(int i=1;i<=n;++i)s[++tot]=a[i],s[++tot]='@';
	for(int i=1;i<=tot;++i){
		if(i>r)while(s[i+dp[i]]==s[i-dp[i]])++dp[i];
		else{
			int j=p*2-i;
			dp[i]=min(r-i,dp[j]);
			while(s[i+dp[i]]==s[i-dp[i]])++dp[i];
		}
		if(i+dp[i]>r){
			r=i+dp[i];
			p=i;
		}
	}
	for(int i=1;i<=n;++i){
		base++;cf[dp[i*2]/2+1]--;
		maxccf=max(maxccf,dp[i*2]-1);
	}
	for(int i=1;i<=(maxccf+1)/2;++i)cf[i]+=cf[i-1];
	for(int i=maxccf;i>=1;i-=2){
		cnt[i]=cf[(i+1)/2]+base;
		if(cnt[i]>=k){
			ans=(ans*ksm(i,k))%mod;
			cout<<ans;
			return 0;
		}
		k-=cnt[i];
		ans=(ans*ksm(i,cnt[i]))%mod;
	}
	cout<<-1;
	return 0;
}