Takahashi and Aoki are going to together construct a sequence of integers.

First, Takahashi will provide a sequence of integers a, satisfying all of the following conditions:

* The length of a is N.
* Each element in a is an integer between 1 and K, inclusive.
* a is a palindrome, that is, reversing the order of elements in a will result in the same sequence as the original.



Then, Aoki will perform the following operation an arbitrary number of times:

* Move the first element in a to the end of a.



How many sequences a can be obtained after this procedure, modulo 10^9+7?

Constraints

* 1≤N≤10^9
* 1≤K≤10^9

Input

The input is given from Standard Input in the following format:


N K


Output

Print the number of the sequences a that can be obtained after the procedure, modulo 10^9+7.

Examples

Input

4 2


Output

6


Input

1 10


Output

10


Input

6 3


Output

75


Input

1000000000 1000000000


Output

875699961
/*Program from Luvwgyx*/
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int mod=1e9+7;
const int maxn=2e3+10;
int n,k,tot,ans,a[maxn],f[maxn];
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void print(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar(x%10+'0');
}
void write(int x){print(x);puts("");}
int power(int a,int b){
    int ret=1;
    for(;b;b>>=1,a=1ll*a*a%mod)
        if(b&1)ret=1ll*ret*a%mod;
    return ret;
}
int main(){
    n=read();k=read();int num=sqrt(n);
    for(int i=1;i*i<n;i++)
        if(!(n%i))a[++tot]=i,a[++tot]=n/i;
    if(num*num==n)a[++tot]=num;sort(a+1,a+tot+1);
    for(int i=1;i<=tot;i++){
        f[i]=power(k,(a[i]+1)>>1);
        for(int j=1;j<i;j++)if(!(a[i]%a[j]))f[i]=(f[i]-f[j]+mod)%mod;
        if(a[i]&1)ans=(ans+1ll*a[i]*f[i])%mod;
        else ans=(ans+a[i]*1ll*power(2,mod-2)%mod*f[i])%mod;
    }write(ans);
    return 0;
}
