题目链接：这里
题意：如题。
解法：对于f(n)，若自然数对(x,y)满足 x+y=n,且gcd(x,y)=1，则这样的数对对数为f(n)
证明f(n)=phi(n)
设有命题 对任意自然数x满足x < n，gcd(x,n)=1等价于gcd(x,y)=1 成立，则该式显然成立，下面证明这个命题。
假设gcd(x,y)=1时，gcd(x,n)=k!=1,则n=n’k,x=x’k,gcd(x,y)=gcd(x,n-x)=gcd(x’k,(n’-x’)k)=k,与假设gcd(x,y)=1不符，故gcd(x,y)=1时，gcd(x,n)=1。同理可证gcd(x,n)=1时，gcd(x,y)=1。
综上，f(n)=phi(n)。
下面那个函数意义就是 n的所有因数的欧拉函数之和，这个数其实就是n本身，不会证明。所以F_k(n)=phi(…phi(n))（求(k+1)/2次phi。

//CF 776E
//f(n) = phi(n)
//g(n) = n

#include <bits/stdc++.h>
using namespace std;
long long eluer(long long n){
    long long ret = n;
    for(long long i = 2; i*i <= n; i++)
    if(n%i == 0){
        ret -= ret/i;
        while(n%i == 0) n /= i;
    }
    if(n > 1) ret -= ret/n;
    return ret;
}
long long n, k;
int main()
{
    cin >> n >> k;
    k = (k + 1) / 2;
    while(k-- && n > 1) n = eluer(n);
    cout << n % 1000000007 << endl;
    return 0;
}