#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define mp make_pair
#define PI pair<int,int>
#define lowbit(i) i&-i
#define For(i,l,r) for(int i=(int)(l);i<=(int)(r);i++)
#define Rep(i,r,l) for(int i=(int)(r);i>=(int)(l);i--)
#define pb push_back
#define fi first
#define se second
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline ll read(){
	ll x = 0; char ch = gc(); bool positive = 1;
	for (; !isdigit(ch); ch = gc())	if (ch == '-')	positive = 0;
	for (; isdigit(ch); ch = gc())	x = x * 10 + ch - '0';
	return positive ? x : -x;
}
inline void write(ll a){
    if(a<0){
    	a=-a; putchar('-');
	}
    if(a>=10)write(a/10);
    putchar('0'+a%10);
}
inline void writeln(ll a){write(a); puts("");}
inline void wri(ll a){write(a); putchar(' ');}
inline ull rnd(){
	ull ans=0; For(i,0,5)ans=ans<<15^rand(); return ans;
}
const int mod=1000000007;
ll mul(ll x,ll y,ll mod){
	return x*y%mod;
}
ll ksm(ll a,ll b,ll mod){
	ll ans=1;
	for(;b;b>>=1){
		if(b&1)ans=mul(ans,a,mod);
		a=mul(a,a,mod);
	}
	return ans;
}
bool MR(ll n){
	const int pr[9]={2,3,5,7,11,13,17,19,23};
	if(n<=1)return 0;
	int cnt=0;
	ll d=n-1; while(!(d&1)){cnt++; d>>=1;}
	For(i,0,8){
		if(n==pr[i])return 1;
		ll x=ksm(pr[i],d,n),p=x;
		For(i,1,cnt){
			x=mul(x,x,n);
			if(x==1&&p!=1&&p!=n-1)return 0;
			p=x;
		}
		if(x!=1)return 0;
	}
	return 1;
}
ll f(ll x,ll c,ll n){return (mul(x,x,n)+c)%n;}
ll get(ll n){
	const int B=500;
	ll c=rand(),x=rand()%n,y=f(x,c,n),p=1;
    while((x!=y)&&((p==1))){
    	ll xx=x,yy=y,cj=1;
    	for(int i=0;i<=B&&x!=y&&cj;i++){
			cj=mul(cj,abs(x-y),n);
			x=f(x,c,n); y=f(f(y,c,n),c,n);
    	}
    	ll t=__gcd(cj,n);
    	if(t==1)continue;
    	else if(cj)return t;
    	else {
 			x=xx; y=yy;
 			for(int i=0;i<=B&&x!=y&&p==1;i++){
 				p=__gcd(abs(x-y),n);
				x=f(x,c,n); y=f(f(y,c,n),c,n);
 			} 
    	}
    }
    return p;
}
map<ll,int> M;
void rho(ll n){
	if(n==1)return;
	if(MR(n)){M[n]++; return;}
	ll t=get(n);
	while(t==1&&t==n)t=get(n);
	rho(t); rho(n/t);
}
int ppp,jz;
ll ans,k,pe[100],pp[100];
ll h(ll x){
	return (x&1)?x:x/2;
}
ll ycl[4][32000];
ll power(ll b){
	ll ans=1;
	For(i,0,3){
		ans=ans*ycl[i][b%jz]%mod; b/=jz;
	}
	return ans;
}
ll g(ll x){
	return power((x+1)>>1);
}
void dfs(int p,ll dq,ll s){
	//cout<<p<<" "<<dq<<" "<<s<<endl;
	if(p>ppp){
		//cout<<p<<" "<<dq<<" "<<s<<endl;
		ans=(ans+h(dq)%mod*g(dq)%mod*(s%mod+mod))%mod; return;
	}
	if(pp[p]!=2)dfs(p+1,dq,s*(1-pp[p]));
	For(i,1,pe[p]){
		//cerr<<(i==pe[p])<<" "<<(1-pp[p])<<endl;
		dq*=pp[p]; dfs(p+1,dq,i==pe[p]?s:s*(1-pp[p]));
	}
}
int main(){
		ll n=read(); k=read();
		jz=pow(n,0.25)+3;
		For(i,0,3){
			ll s;
			if(i)s=ycl[i-1][jz]; else s=k%mod;
			For(j,ycl[i][0]=1,jz)ycl[i][j]=ycl[i][j-1]*s%mod;
		}
		M.clear(); rho(n); ans=ppp=0;
		for(auto i:M){pp[++ppp]=i.fi; pe[ppp]=i.se;}
		dfs(1,1,1);
		cout<<ans<<endl;
}
/*
f(i)=\sum g(j)\mu(i/j)
1
9311702400 7367823578 1015387267
3 2 1000000005
3 3 1000000007
4 2 1000000009
4 3 1000000011
4 4 1000000013
5 5 1000000015
7 7 1000000017
9 9 1000000019

*/

Measured memory_bytes: 256