#include <stdio.h>

#define MOD 9901

int A[1000], Nr[1000];
int i, act,a , b;
int Ans;

inline int put(int N, int K)
{
	int rez = 1;
	for (int i = 0; (1<<i) <= K; ++i){
		if (K & (1<<i))
			rez = (1LL * rez * N) % MOD;
		N = (1LL * N * N) % MOD;
	}
	return rez;
}

int main()
{
	freopen("sumdiv.in","r",stdin);
	freopen("sumdiv.out","w",stdout);
	
	scanf("%d %d",&a, &b);
	for (i = 2; i * i <= a; ++i){
		if (a % i != 0) continue;
		A[++A[0]] = i;
		while (a % i == 0){
			a /= i;
			++Nr[A[0]];
		}
	}
	
	if (a != 1){
		A[++A[0]] = a;
		Nr[A[0]] = 1;
	}
	
	for (i = 1; i <= A[0]; ++i)
		Nr[i] *= b;
	
	Ans = 1;
	for (i = 1; i <= A[0]; ++i){
		act = put(A[i], Nr[i] + 1);
		act = (act - 1 + MOD) % MOD;
		act = (1LL * act * put(A[i]-1, MOD-2));
		Ans = (1LL * Ans * act) % MOD;
	}
	
	printf("%d\n", Ans);
	
	return 0;
}