如题

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5, M = 9901;
int ksm(int a, int k) {
	int res = 1;
	while (k) {
		if (k & 1)
			res = res * a % M;
		a = a * a % M;
		k >>= 1;
	}
	return res;
}
ll a, b, p[N], c[N], k, ans = 1;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> a >> b;
	if (b == 0) {
		cout << "1\n";
		return 0;
	}
	for (int i = 2; i * i <= a; i++) {
		if (a % i == 0) {
			p[++k] = i;
			while (a % i == 0) {
				a /= i;
				c[k]++;
			}
		}
	}
	if (a > 1) {
		p[++k] = a;
		c[k]++;
	}
	for (int i = 1; i <= k; i++)
		c[i] *= b;
	for (int i = 1; i <= k; i++) {
		if ((p[i] - 1) % M != 0) {
			ans *= ksm(p[i], c[i] + 1) - 1;
			ans = (ans + M) % M;
			ans *= ksm(p[i] - 1, M - 2);
			ans %= M;
		} else {
			ans = ans * (c[i] + 1) % M;
		}
	}
	cout << ans << '\n';
	return 0;
}