别人40ms，我1.20s

我的code,请求帮助

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 3e6 + 10, mod = 19930726;
int p[N], cnt;
int ans[N];
char a[N], b[N];
int n,k;
void init()
{
	//int len = strlen(a);
	cnt = 0;
	b[cnt ++] = '$', b[cnt ++] = '#';
	for(int i = 0; i < n; i ++)
	{
		b[cnt ++] = a[i], b[cnt ++] = '#';
	}
	b[cnt ++] = '^';
}
void Man()
{
	int mr = 0, mid = 0;
	for(int i = 1; i < cnt; i ++)
	{
		//cout << i << endl;
		if(i < mr) p[i] = min(p[2 * mid - 1], mr - i);
		else p[i] = 1;
		while(b[i - p[i]] == b[i + p[i]]) p[i] ++;
		if(i + p[i] > mr)
		{
			mr = i + p[i];
			mid = i;
		}
		if((p[i] - 1) % 2 == 1) ans[p[i] - 1] ++;
	}
}
int qpow(int a, int b)
{
	int res = 1;
	if(a == 1) return 1;
	while(b)
	{
		if(b & 1) res = res * a % mod;
		b >>= 1;
		a = a * a % mod;
	}
	return res;
}
int cmp(int x, int y)
{
	return x > y;
}
signed main()
{
	//freopen("P1659_18.in.txt","r",stdin);
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> k;
	cin >> a;
	init();
	Man();
	int anss = 1;
	int sum = 0;
	for(int i = n; i >= 1; i --)
	{
		if(i % 2 == 0) continue;
		sum += ans[i];
		if(k >= sum)
		{
			anss = (anss * qpow(i, sum) % mod) % mod;
			k -= sum;
		}
		else
		{
			anss = (anss * qpow(i, k) % mod) % mod;
			k -= sum;
			break;
		}
	}
	if(k > 0) cout << -1 << endl;
	else cout << anss << endl;
	
	
	return 0;
}