The Holmes children are fighting over who amongst them is the cleverest.

Mycroft asked Sherlock and Eurus to find value of f(n), where f(1) = 1 and for n ≥ 2, f(n) is the number of distinct ordered positive integer pairs (x, y) that satisfy x + y = n and gcd(x, y) = 1. The integer gcd(a, b) is the greatest common divisor of a and b.

Sherlock said that solving this was child's play and asked Mycroft to instead get the value of $g(n) = \sum_{d|n} f(n / d)$. Summation is done over all positive integers d that divide n.

Eurus was quietly observing all this and finally came up with her problem to astonish both Sherlock and Mycroft.

She defined a k-composite function F_{k}(n) recursively as follows:

$F_{k}(n) = \left\{\begin{array}{ll}{f(g(n)),} & {\text{for} k = 1} \\{g(F_{k - 1}(n)),} & {\text{for} k > 1 \text{and} k \operatorname{mod} 2 = 0} \\{f(F_{k - 1}(n)),} & {\text{for} k > 1 \text{and} k \operatorname{mod} 2 = 1} \end{array} \right.$

She wants them to tell the value of F_{k}(n) modulo 1000000007.


-----Input-----

A single line of input contains two space separated integers n (1 ≤ n ≤ 10^12) and k (1 ≤ k ≤ 10^12) indicating that Eurus asks Sherlock and Mycroft to find the value of F_{k}(n) modulo 1000000007.


-----Output-----

Output a single integer — the value of F_{k}(n) modulo 1000000007.


-----Examples-----
Input
7 1

Output
6
Input
10 2

Output
4


-----Note-----

In the first case, there are 6 distinct ordered pairs (1, 6), (2, 5), (3, 4), (4, 3), (5, 2) and (6, 1) satisfying x + y = 7 and gcd(x, y) = 1. Hence, f(7) = 6. So, F_1(7) = f(g(7)) = f(f(7) + f(1)) = f(6 + 1) = f(7) = 6.

Difficulty: competition

Starter code:

Solutions:
from math import sqrt, ceil

MAX_N = 10 ** 6 * 2 


prime = []
isPrime = [True for i in range(MAX_N)]

for i in range(2, MAX_N):
    if isPrime[i]:
        prime.append(i)
        for j in range(i * i, MAX_N, i):
            isPrime[j] = False


def factor(a):
    divs = []
    for i in prime:
        cnt = 0
        while a % i == 0:
            a //= i
            cnt += 1

        if cnt:
            divs.append((i, cnt,))

    if a > 1:
        divs.append((a, 1,))

    return divs


def f(n):
    ans = 1
    for div in factor(n):
        ans *= div[0] ** (div[1] - 1) * (div[0] - 1)

    return ans

def g(n):
    return n

def F(n, k):
    cur = n
    for i in range(1, k + 1):
        #print(i)
        #print(factor(cur))
        if i == 1:
            cur = f(g(cur))
        elif i % 2 == 0:
            cur = g(cur)
        else:
            cur = f(cur)

        #print(i, cur)

        if cur == 1:
            break

    return cur % (10 ** 9 + 7)

n, k = [int(i) for i in input().split(' ')]
#print(factor(n - 1))
print(F(n, k))


MOD = 1000000007
def phi(n):
    res = n
    for i in range(2,int(n**(0.5)+1)):
        if n % i == 0:
            while n % i == 0:
                n = n//i
            res -= res//i
    if n > 1:
        res -= res//n
    return res

n,k = list(map(int,input().split()))
k = (k+1)//2
ans = n
for _ in range(k):
    if ans > 1:
        ans = phi(ans)
    else:
        break
print(ans % MOD)


N = 10 ** 6 * 2 
MOD = 1000000007
prime = []
isPrime = [True for i in range(N)]
for i in range(2, N):
    if isPrime[i]:
        prime.append(i)
        for j in range(i * i, N, i):
            isPrime[j] = False
def phi(n):
    ans = 1
    for i in pf(n):
        ans *= pow(i[0],i[1]-1)*(i[0]-1)
    return ans
def pf(n):
    for i in prime:
        cnt = 0
        if n % i == 0:
            while n % i == 0:
                n //= i
                cnt += 1
            yield (i,cnt)
    if n > 1:
        yield (n,1)
n,k = list(map(int,input().split()))
k = (k+1)//2
ans = n
for i in range(k):
    ans = phi(ans)
    if ans == 1:
        break
print(ans % MOD)


phi = [0 for i in range(100100)]
phi[1] = 1
for i in range(2, 100050):
    if (phi[i] == 0):
        for j in range(i, 100051, i):
            if (phi[j] == 0):
                phi[j]=j
            phi[j] = phi[j]//i*(i-1)

def Fenjie(n):
    k = {}
    if (n == 1):
        return {}
    a = 2
    while (n >= 2):
        b = n%a
        if (a*a > n):
            if (n in k):
                k[n] += 1
            else:
                k[n] = 1
            break
        if (b == 0):
            if (a in k):
                k[a] += 1
            else:
                k[a] = 1
            n = n//a
        else:
            a += 1
    return k

def Euler(k):
    if (len(k) == 0):
        return 1
    ans = 1
    for i in k:
        s = k[i]
        ans *= pow(i, s)
        ans = ans//i*(i-1)
    return ans

n, k = list(map(int, input().split()))
k = (k+1)//2
while (k):
    k -= 1
    n = Euler(Fenjie(n))
    if (n==1):
        break
print(n%(10**9+7))


import math
def phi(n):
    res = n
    for i in range(2, int(math.sqrt(n)) + 1):
        if(n % i == 0):
            while(n % i == 0):
                n /= i
            res -= res/i
    if(n > 1):
        res -= int(res / n)
    return res
n, k = map(int, input().split())
res = n
k = int((k + 1) / 2)
while(res != 1 and k != 0):
    res = phi(res)
    k -= 1
print("{}".format(int(res % (1e9 + 7))))