#include <bits/stdc++.h>  
using namespace std;  
typedef long long ll;  
const ll mod=1e9+7;  
const int N=2e5+20;  
vector<ll> v;  
ll n,k,dp[2500];  
ll powmod(ll x,ll n)  
{  
    ll s=1;  
    while(n)  
    {  
        if(n&1)  
            s=(s*x)%mod;  
        n>>=1;  
        x=(x*x)%mod;  
    }  
    return s;  
}  
void init()  
{  
    v.clear();  
    for(ll i=1;i*i<=n;i++)  
    {  
        if(n%i==0)  
        {  
            v.push_back(i);  
            if(i*i!=n)  
                v.push_back(n/i);  
        }  
    }  
    sort(v.begin(),v.end());  
}  
int main()  
{  
    while(cin>>n>>k)  
    {  
        init();  
        ll ans=0;  
        for(int x=0;x<v.size();x++)  
        {  
            dp[x]=powmod(k,(v[x]+1)/2);  
            for(int y=0;y<x;y++)  
            {  
                if(v[x]%v[y]==0)  
                    dp[x]=(dp[x]-dp[y]+mod)%mod;      
            }     
            if(v[x]%2)  
                ans=(ans+(dp[x]*v[x])%mod)%mod;  
            else  
                ans=(ans+(dp[x]*v[x]/2)%mod)%mod;  
        }  
        cout<<ans<<endl;  
    }  
    return 0;  
}  
