#include <bits/stdc++.h>
using namespace std;
using ll = long long;

constexpr int md = 100003;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll n, k;
	cin >> n >> k;
	if(k == 1){
		cout << n << '\n';
		return 0;
	}
	k -= 2;
	int cur = 0;
	for(int i = 1; i <= n; i++){
		if(n % i == 0) (cur += i) %= md;
	}
	vector<int> dp(md, 1);
	for(int i = 2; i < md; i++){
		for(int j = i; j < md; j += i){
			dp[j] += i;
			if(dp[j] >= md) dp[j] -= md;
		}
	}
	while(k){
		if(k & 1) cur = dp[cur];
		vector<int> ndp(md);
		for(int i = 0; i < md; i++){
			ndp[i] = dp[dp[i]];
		}
		swap(dp, ndp);
		k /= 2;
	}
	cout << cur << '\n';
}