CF776E.The Holmes Children

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 . 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:

She wants them to tell the value of F__k(n) modulo 1000000007.

福尔摩斯家的孩子们正在争论，他们之中究竟谁最聪明。

迈克罗夫特让夏洛克和欧洛斯计算函数 $ f(n) $ 的值，其中 $ f(1) = 1 $，而对于 $ n \geq 2 $，$ f(n) $ 表示满足 $ x + y = n $ 且 $ \gcd(x, y) = 1 $ 的互异的有序正整数对 $ (x, y) $ 的个数。此处 $ \gcd(a, b) $ 表示 $ a $ 与 $ b $ 的最大公约数。

夏洛克称这道题小菜一碟，于是请迈克罗夫特改为计算 的值。该求和遍历所有能整除 $ n $ 的正整数 $ d $。

欧洛斯一直安静地旁观这一切，最后提出了她自己的问题，以令夏洛克和迈克罗夫特都大为惊叹。

她递归地定义了一个 $ k $-复合函数 $ F_k(n) $，如下所示：

她要求他们计算 $ F_k(n) $ 对 $ 1000000007 $ 取模的结果。

A single line of input contains two space separated integers n (1 ≤ n ≤ 1012) and k (1 ≤ k ≤ 1012) indicating that Eurus asks Sherlock and Mycroft to find the value of F__k(n) modulo 1000000007.

一行输入包含两个以空格分隔的整数 $n$（$1 \leq n \leq 10^{12}$）和 $k$（$1 \leq k \leq 10^{12}$），表示 Eurus 要求 Sherlock 和 Mycroft 计算 $F_k(n)$ 对 $1000000007$ 取模的值。

Output a single integer — the value of F__k(n) modulo 1000000007.

输出一个整数——$F_k(n)$ 对 $1000000007$ 取模的结果。

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.

第一种情况中，有 6 个互不相同的有序对 $(1,\,6)$、$(2,\,5)$、$(3,\,4)$、$(4,\,3)$、$(5,\,2)$ 和 $(6,\,1)$ 满足 $x\,+\,y\,=\,7$ 且 $\gcd(x,\,y)\,=\,1$。因此，$f(7)\,=\,6$。于是，$F_1(7)\,=\,f(g(7))\,=\,f(f(7)\,+\,f(1))\,=\,f(6\,+\,1)\,=\,f(7)\,=\,6$。