HDU-4983 Goffi and GCD
#include<bits/stdc++.h>
#define me(a,x) memset(a,x,sizeof(a))
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
#define sc scanf
#define itn int
#define STR clock_t startTime = clock();
#define END clock_t endTime = clock();cout << double(endTime - startTime) / CLOCKS_PER_SEC *1000<< "ms" << endl;
using namespace std;
const int N=1e6;
const long long mod=1e9+7;
const long long mod2=998244353;
const int oo=0x7fffffff;
const int sup=0x80000000;
typedef long long ll;
typedef unsigned long long ull;
template <typename it>void db(it *begin,it *end){while(begin!=end)cout<<(*begin++)<<" ";puts("");}
template <typename it>
string to_str(it n){string s="";while(n)s+=n%10+'0',n/=10;reverse(s.begin(),s.end());return s;}
template <typename it>int o(it a){cout<<a<<endl;return 0;}
ll mul(ll a,ll b,ll c){ll ans=0;for(;b;b>>=1,a=(a+a)%c)if(b&1)ans=(ans+a)%c;return ans;}
ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=mul(a,a,c))if(b&1)ans=mul(ans,a,c);return ans;}
int main(){
itn n,k;
while(~sc("%d%d",&n,&k)){
if(n==1||k==2){
printf("1\n");continue;
}
if(k>2){
printf("0\n");continue;
}
ll ans=1;
for(int i=2;1ll*i*i<=n;i++){
if(n%i==0){
itn cnt=0;
ll p=1;
while(n%i==0)n/=i,cnt++,p*=i;
if(cnt>=2){
ll res=1LL*(i-1)*(i-1)*(cnt-1)%mod+2LL*(i-1)*i%mod;
res%=mod;
ans=ans*res%mod*(p/i/i)%mod;
}else {
ans=ans*(2LL*(i-1)%mod)%mod;
}
}
}
if(n>1)ans=ans*2LL*(n-1)%mod;
printf("%lld\n",ans);
}
}