福尔摩斯的孩子们正在为谁最聪明而争吵。
Mycroft 要求 Sherlock 和 Eurus 求 f(n) 的值,其中 f(1) = 1,且 n ≥ 2,f(n) 是满足 x + y = n 且 gcd(x, y) = 1 的不同有序正整数对 (x, y) 的数量。整数 gcd(a, b) 是 a 和 b 的最大公约数。
Sherlock 说解决这个问题很简单,并要求 Mycroft 获取 $$g(n) = \sum_{d|n} f\left(\frac{n}{d}\right)$$ 的值。对整除 n 的所有正整数 d 进行求和。
Eurus静静地观察着这一切,最终提出了让Sherlock和Mycroft都惊讶的问题。
她递归地定义了一个k复合函数Fk(n)如下:
$$$$
她希望他们说出 Fk(n) 模 1000000007 的值。
输入
单行输入包含两个空格分隔的整数 n (1 ≤ n ≤ 1012) 和 k (1 ≤ k ≤ 1012),表示 Eurus 要求 Sherlock 和 Mycroft 求 Fk(n) 模 1000000007 的值。
输出
输出单个整数——Fk(n) 模 1000000007 的值。
示例
输入 #1
7 1
输出 #1
6
输入 #2
10 2
输出 #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。