#include<bits/stdc++.h>
using namespace std;
int a, b;
const int MOD = 9901;
int qpow(int x, int n){
	int ans = 1;
	x %= MOD;
	while(n){
		if(n & 1) ans = ans * x % MOD;
		x = x * x % MOD;
		n >>= 1;
	}
	return ans;
}

int main(){
	cin >> a >> b;
	if(a % 9901 == 0){
		cout << 0 << endl;
		return 0;
	}
	
	int ans = 1;
	for(int i = 2; i <= a / i; i++){
		if(a % i == 0){
			int k = 0;
			
			while(a % i == 0){
				a /= i;
				k++;
			}
			
			if((i - 1) % MOD == 0){
				ans = ans * (i + 1) % MOD;
				continue;
			}
			
			ans = (ans * (qpow(i, (b % (MOD - 1) * k % (MOD - 1) + 1) % (MOD - 1)) - 1) % MOD * qpow(i - 1, MOD - 2) % MOD) % MOD;
		}
	}
	
	if(a > 1){
		if((a - 1) % MOD == 0){
			ans = ans * (1 + a) % MOD;
		}else ans = (ans * (qpow(a, (b % (MOD - 1) + 1) % (MOD - 1)) - 1) % MOD * qpow(a - 1, MOD - 2) % MOD);
	}
	cout << ans;
	return 0;
}