#include <iostream>

#define MOD 9901

using namespace std;

int N, K;

int logpow(int A, int B) {
	int R(1);
	for (int i = 1 << 30; i > 0; i >>= 1) {
		R = (R * R) % MOD;
		if (i & B)
			R = (R * A) % MOD;
	}
	return R;
}

int progresie(int p, int q) {
	int a = (logpow(p, q+1) - 1 + MOD) % MOD;
	int b = p - 1;
	
	int c;
	for (c = 1; c <= MOD; ++c)
		if ((c * b) % MOD == a)
			break;
	return c % MOD;
}

int main(int argc, char *argv[]) {
	FILE *fi = fopen("sumadiv.in", "r");
	fscanf(fi, "%d %d", &N, &K);
	fclose(fi);

	int S(0);
	int d(2);
	while (d*d <= N) {
		if (N % d == 0) {
			int p;
			for (p = 0; N % d == 0; ++p)
				N /= d;
			S = (S + progresie(d % MOD, K*p)) % MOD;
		}
		++d;
	}
	if (N > 1)
		S = (S + progresie(N % MOD, K)) % MOD;

	FILE *fo = fopen("sumadiv.out", "w");
	fprintf(fo, "%d\n", S);
	fclose(fo);

	return 0;
}