#include <iostream>
#include <vector>
#include <print>

using namespace std;

const int MOD = 100003;
const int MAX = 3000005;

vector<int> sigma(MAX, 0);

void precompute() {
    for (int i = 1; i < MAX; ++i) {
        for (int j = i; j < MAX; j += i) {
            sigma[j] = (sigma[j] + i) % MOD;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    precompute();

    long long n, k;
    if (!(cin >> n >> k)) return 0;

    vector<long long> visited(MOD, -1);
    vector<long long> history;

    long long curr = n;
    long long step = 1;

    while (step <= k) {
        if (curr < MOD) {
            if (visited[curr] != -1) {
                long long cycle_start = visited[curr];
                long long cycle_len = step - cycle_start;
                
                // 正しい遷移数 (k - step) を使って余りを計算
                long long rem_steps = (k - step) % cycle_len;
                long long ans_idx = cycle_start - 1 + rem_steps;
                
                std::println("{}", history[ans_idx]);
                return 0;
            }
            visited[curr] = step;
        }

        history.push_back(curr);

        if (step == k) break;
        curr = sigma[curr];
        step++;
    }

    std::println("{}", curr);

    return 0;
}