rt

#include <bits/stdc++.h>
#define int long long
#define mod 19930726
using namespace std;
int n,len,k,mr,mid,hw[2000005],cnt[2000005],ans;
char a[1000005],s[2000005];
int qpow(int x,int y){
	int now=1,base=x;
	while(y){
		if(y%2) now=now*base%mod;
		base=base*base%mod;
		y=y/2;
	}
	return now;
}
signed main(){
	cin >>len>>k;
	//for(int i=1;i<=len;i++) cin >>a[i];
	cin >>a+1;
	for(int i=1;i<=len;i++){
		s[i*2-1]='#';
		s[i*2]=a[i];
	}
	n=(len*2)+1;
	s[n]='#';
	for(int i=1;i<=n;i++){
		if(i<mr) hw[i]=min(hw[mid*2-i],mr-i);
		else hw[i]=1;
		while(s[i+hw[i]]==s[i-hw[i]]) hw[i]++;
		if(hw[i]+i>mr){
			mr=hw[i]+i;
			mid=i;
		}
		if((hw[i]-1)%2){
			cnt[hw[i]-1]++;
		}
	}
	int sum=0;
	ans=1;
	for(int i=len;i>=1;i--){
		if(i%2==0) continue;
		sum+=cnt[i];
		if(k>=sum){
			ans=(ans*qpow(i,sum))%mod;
			k-=sum;
		}
		else{
			ans=(ans*qpow(i,k))%mod;
			k-=sum;
			break;
		}
	}
	if(k>0) cout <<-1;
	else cout <<ans;
	return 0;
}

https://www.luogu.com.cn/record/133702282