Дети Холмс сражаются за право считаться самым умным.
Майкрофт попросил Шерлока и Эвр найти значение f(n), где f(1) = 1, а для n ≥ 2, f(n) равно количеству различных упорядоченных пар положительных целых чисел (x, y) таких, что x + y = n и gcd(x, y) = 1. Число gcd(a, b) равно наибольшему общему делителю a и b.
Шерлок сказал, что это было слишком просто и попросил Майкрофта найти значение 
. Суммирование проводится по всем положительным целым числам d, делящим n.
Эвр наблюдала это, не проронив ни слова, и в итоге задала Майкрофту и Шерлоку свою задачу.
Она определила сложную функцию k-го порядка Fk(n) так:
Она хочет, чтобы братья нашли значение Fk(n) по модулю 1000000007.
В единственной строке находятся два целых числа n (1 ≤ n ≤ 1012) и k (1 ≤ k ≤ 1012), показывающие, что Эвр попросила Шерлока и Майкрофта найти значение Fk(n) по модулю 1000000007.
Выведите одно целое число — значение Fk(n) по модулю 1000000007.
7 1
6
10 2
4
В первом примере есть 6 различных упорядоченных пар (1, 6), (2, 5), (3, 4), (4, 3), (5, 2) и (6, 1), удовлетворяющих x + y = 7 и gcd(x, y) = 1. Поэтому f(7) = 6. В итоге, F1(7) = f(g(7)) = f(f(7) + f(1)) = f(6 + 1) = f(7) = 6.
