MOD = 100003
N,K = list(map(int,input().split()))
K -= 2

if(K == -1):
    print(N)
    exit()

next = [0] * MOD
for i in range(1,MOD):
    now = i
    while(now < MOD):
        next[now] += i
        next[now] %= MOD
        now += i

START = 0
for i in range(1,N+1):
    if(N%i == 0):
        START += i

# https://qiita.com/Kept1994/items/ea91c057b0e552323da3
MAX = 10**18+100
import math
# 二次元配列作成
dv = []
for _ in range(int(math.log2(MAX)) + 1):
   l = [0] * MOD
   dv.append(l)

# dv[0][0:X]を初期化
dv[0] = next[:]


# ダブリングで表を構築
for k in range(1, int(math.log2(MAX)) + 1):
   for n in range(MOD):
       dv[k][n] = dv[k - 1][dv[k - 1][n]]

# 解を求めるゾーン
a = []
for i in range(int(math.log2(MAX)) + 1):
    if K>>i & 1:
        a.append(i)

now = START
for i in a:
    now = dv[i][now]
print(now)