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

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

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