#include <bits/stdc++.h>
#include <atcoder/all>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
using namespace atcoder;
using mint = modint;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; i--)
#define rrep1(i, n) for (int i = (int)(n) - 1; i >= 1; i--)
#define ll long long
#define double long double
#define ull unsigned long long
#define ALL(v) (v).begin(), (v).end()
#define NP next_permutation
#define PLL pair<long long, long long>
#define VL vector<long long>
#define VVL vector<vector<long long>>
#define VVVL vector<vector<vector<long long>>>
#define VPLL vector<pair<long long, long long>>
#define STL set<long long>
#define MPLL map<long long, long long>
#define SP fixed << setprecision(12)
#define hashmap unordered_set
#define popcount __builtin_popcountll

constexpr ll inf = 4001001001001001001ll;
constexpr ll mod = 100003;  ///* 1000000007; //*/ 998244353;
constexpr double pi = 3.141592653589793;
constexpr double eps = 0.00000000001;
vector<ll> d8x = {1, 1, 0, -1, -1, -1, 0, 1};
vector<ll> d8y = {0, 1, 1, 1, 0, -1, -1, -1};
vector<ll> d4x = {1, 0, -1, 0};
vector<ll> d4y = {0, 1, 0, -1};
// 小数出力
// cout << setprecision(12);
// struct
typedef tree<
    int,
    null_type,
    less<int>,
    rb_tree_tag,
    tree_order_statistics_node_update>
    ordered_set;
struct Ruiseki {
  vector<ll> v;
  Ruiseki(vector<ll>& vec) {
    ll n = vec.size();
    v.resize(n + 1);
    rep(i, n) v[i + 1] = v[i] + vec[i];
  }
  ll get(ll l, ll r) {  // 開区間になりました
    return v[r] - v[l];
  }
};
// max
template <typename T1, typename T2>
inline bool chmax(T1& a, T2 b) { return a < b && (a = b, true); }
// min
template <typename T1, typename T2>
inline bool chmin(T1& a, T2 b) { return a > b && (a = b, true); }
// join
template <typename T>
string join(vector<T>& vec, const string& sp = " ") {
  int si = vec.size();
  if (si == 0) {
    return "";
  } else {
    stringstream ss;
    rep(i, si - 1) {
      ss << vec[i] << sp;
    }
    ss << vec[si - 1];
    return ss.str();
  }
}
// print
template <typename T>
void pr_single(const T& x) {
  if constexpr (requires { x.val(); }) cout << x.val();
  else if constexpr (requires { typename T::value_type; } && !requires { x.substr(0); }) {
    using elem_type = typename T::value_type;
    constexpr bool is_container_of_container =
        requires { typename elem_type::value_type; } &&
        !requires(elem_type e) { e.substr(0); };
    for (int i = 0; i < (int)x.size(); i++) {
      pr_single(x[i]);
      if (i != (int)x.size() - 1) {
        if constexpr (is_container_of_container) {
          cout << "\n";
        } else {
          cout << " ";
        }
      }
    }
  } else if constexpr (requires { x.first; x.second; }) {
    pr_single(x.first);
    cout << " ";
    pr_single(x.second);
  } else if constexpr (requires { cout << x; }) {
    cout << x;
  }
}
void pr() { cout << endl; }
template <typename Head, typename... Tail>
void pr(const Head& head, const Tail&... tail) {
  pr_single(head);
  if constexpr (sizeof...(tail) > 0) {
    cout << " ";
    pr(tail...);
  } else
    cout << endl;
}
// Yes
string Yes(bool x) {
  if (x) return "Yes\n";
  return "No\n";
}
string YES(bool x) {
  if (x) return "YES\n";
  return "NO\n";
}
ll Digit(ll n) {
  ll ans = 0;
  while (n > 0) {
    n /= 10;
    ans++;
  }
  return ans;
}
bool in_range(int l, int x, int r) {  // 閉区間
  return ((l <= x) && (x <= r)) || ((r <= x) && (x <= l));
}
int div_ceil(int x, int y) {
  return (x + y - 1) / y;
}
void yakubun(ll& a, ll& b) {
  if (a < 0) {
    a = -a;
    b = -b;
  }
  if (a == 0) {
    b = 1;
    return;
  }
  if (b == 0) {
    a = 1;
    return;
  }
  ll g = gcd(abs(a), abs(b));
  a /= g;
  b /= g;
  // pr(a, b);
}
void swap(pair<ll, ll>& p) {
  auto [a, b] = p;
  p = {b, a};
}
ll _sqrt(ll x) {
  ll a = sqrt(x);
  while ((a + 1) * (a + 1) <= x) a++;
  while (a * a > x) a--;
  return a;
}
ll _pow(ll x, ll n) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) res *= x;
    x *= x;
    n >>= 1;
  }
  return res;
}
ll bs(ll l, ll r, function<bool(ll)> f) {  // l-> false, r->true
  while (r - l > 1) {
    ll mid = l + (r - l) / 2;
    if (f(mid)) r = mid;
    else
      l = mid;
  }
  return r;
}
ll op(ll a, ll b) {
  return a + b;
}
ll e() {
  return 0;
}
void solve() {
}
ll calc(ll n) {
  ll ans = 0;
  rep1(i, _sqrt(n) + 1) {
    if (n % i == 0) {
      ans += i + n / i;
    }
  }
  return ans % 100003;
}
signed main() {
  mint::set_mod(100003);
  ll n, k;
  cin >> n >> k;
  vector<vector<ll>> dp(61, vector<ll>(100003, 0));
  rep1(i, 100003) {
    for (ll j = i; j < 100003; j += i) {
      dp[0][j] += i;
      dp[0][j] %= mod;
    }
  }
  // pr(dp[0]);
  rep1(i, 61) {
    rep1(j, 100003) {
      dp[i][j] = dp[i - 1][dp[i - 1][j]];
    }
  }
  k--;
  if (k == 0) {
    cout << n << endl;
    return 0;
  }
  ll now = calc(n);
  k--;
  rep(i, 61) {
    if ((k >> i) & 1ll) {
      now = dp[i][now];
    }
  }
  pr(now);
}