A10792 | 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$ .

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 a single integer — the value of $F_{k}(n)$ modulo $1000000007$ .