n, k = list(map(int, input().split()))
A = []
C = {}
a = n
mod = 10**5+3
N = 3*10**6+10
dp = [0] * (N+1)
for u in range(1, N+1):
    for v in range(u, N+1, u):
        dp[v] += u
        dp[v] %= mod
while not a in C:
    C[a] = len(A)
    A.append(a)
    a = dp[a]
k -= 1
#print(A)
#print(a)
#print(len(A))
if k < len(A):
    print(A[k])
else:
    k -= len(A)
    le = len(A)-C[a]
    print(A[C[a]+k%le])