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: HARD
Tags: Number theory

Mathematics

Starter code:

Solutions:
mod = 1000000000.0 + 7

def Phi(n):
	phi = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			while n % i == 0:
				n //= i
			phi -= phi // i
		i += 1
	if n > 1:
		phi -= phi // n
	return phi

def f(n):
	return Phi(n)

def g(n):
	return n
(n, k) = map(int, input().split())
ans = n
k = (k + 1) // 2
while k != 0:
	ans = Phi(ans)
	if ans == 1:
		break
	k -= 1
ans = int(ans % mod)
print(ans)


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):
		if i == 1:
			cur = f(g(cur))
		elif i % 2 == 0:
			cur = g(cur)
		else:
			cur = f(cur)
		if cur == 1:
			break
	return cur % (10 ** 9 + 7)
(n, k) = [int(i) for i in input().split(' ')]
print(F(n, k))


import math

def f_k_n(n, k):
	k = int((k + 1) / 2)
	while n > 1 and k:
		n = phi_improved(n)
		k -= 1
	return n

def phi(n):
	p = 1
	for i in range(2, n):
		if gcd(i, n) == 1:
			p += 1
	return p

def phi_improved(n):
	prime_fact = find_prime_factors(n)
	result = n
	for p in prime_fact:
		result *= 1 - 1 / p
	return int(result)

def find_prime_factors(n):
	l = []
	temp_n = n
	if temp_n % 2 == 0:
		l.append(2)
	while temp_n % 2 == 0:
		temp_n = temp_n / 2
	i = 3
	last_i = 0
	while i <= math.sqrt(n):
		if temp_n % i == 0:
			if last_i != i:
				l.append(i)
				last_i = i
			temp_n = temp_n / i
		else:
			i += 2
	if temp_n > 2:
		l.append(int(temp_n))
	return l

def gcd(x, y):
	r = x % y
	while r != 0:
		x = y
		y = r
		r = x % y
	return y

def find_dividers(n):
	d = 2
	dividers = [1]
	while d < math.sqrt(n):
		if n % d == 0:
			dividers.append(d)
		d += 1
	return dividers

def main():
	(n, k) = [int(i) for i in input().split()]
	print(str(f_k_n(n, k) % 1000000007))
main()


import math

def f_k_n(n, k):
	k = int((k + 1) / 2)
	while n > 1 and k:
		n = phi_improved(n)
		k -= 1
	return n

def phi_improved(n):
	prime_fact = find_prime_factors(n)
	result = n
	for p in prime_fact:
		result *= 1 - 1 / p
	return int(result)

def find_prime_factors(n):
	l = []
	temp_n = n
	if temp_n % 2 == 0:
		l.append(2)
	while temp_n % 2 == 0:
		temp_n = temp_n / 2
	i = 3
	last_i = 0
	while i <= math.sqrt(n):
		if temp_n % i == 0:
			if last_i != i:
				l.append(i)
				last_i = i
			temp_n = temp_n / i
		else:
			i += 2
	if temp_n > 2:
		l.append(int(temp_n))
	return l

def main():
	(n, k) = [int(i) for i in input().split()]
	print(str(f_k_n(n, k) % 1000000007))
main()


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 int(res)

def F(n, k):
	k = int((k + 1) / 2)
	res = n
	while k != 0:
		res = phi(res)
		if res == 1:
			break
		k -= 1
	return int(res % (10 ** 9 + 7))
(n, k) = [int(i) for i in input().split(' ')]
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) = 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)


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 % (1000000000.0 + 7))))


mod = 1000000000.0 + 7

def primeFactors(n):
	factores = []
	if n % 2 == 0:
		exp = 0
		while n % 2 == 0:
			exp += 1
			n //= 2
		factores.append((2, exp))
	i = 3
	while i * i <= n:
		if n % i == 0:
			exp = 0
			while n % i == 0:
				exp += 1
				n //= i
			factores.append((i, exp))
		i += 2
	if n > 2:
		factores.append((n, 1))
	return factores

def Phi(n):
	phi = 1
	for fact in primeFactors(n):
		phi *= fact[0] ** (fact[1] - 1) * (fact[0] - 1)
	return phi

def f(n):
	return Phi(n)

def g(n):
	return n
(n, k) = map(int, input().split())
ans = n
k = (k + 1) // 2
while k != 0:
	ans = Phi(ans)
	if ans == 1:
		break
	k -= 1
ans = int(ans % mod)
print(ans)