测评记录：https://www.luogu.com.cn/record/100406388

好像是除了 $0$ 还是什么qwq

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 5;
LL T, n, k, cnt, phi, mod, f1[N], f2[N];
char ch;
LL query(LL k) {
	return f1[k % cnt] * f2[k / cnt] % mod;
}
LL getPhi(LL k) {
	LL res = 1;
	for (int i = 2; i * i <= k; i ++) {
		if (k % i) continue;
		res *= i - 1, k /= i;
		while (k % i == 0) k /= i, res *= i;
	}
	if (k) res *= k - 1;
	return res;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> mod, phi = getPhi(mod);
	while (cin >> ch) k = (k * 10 + ch - '0') % phi;
	cnt = sqrt(phi * 2) + 1, f1[0] = f2[0] = 1;
	for (int i = 1; i <= cnt; i ++) f1[i] = f1[i - 1] * n % mod;
	for (int i = 1; i <= cnt; i ++) f2[i] = f2[i - 1] * f1[cnt] % mod;
	cout << query(k + phi) << ' ';
	return 0;
}