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
#include <cstdio>
#include <cmath>
#define repu(i,x,y) for (int i=x; i<=y; ++i)
#define id(x) ((x)<=sqrtn?x:sqrtn+n/(x))
using namespace std;

typedef long long LL;
const int p=1000000007;
int n,k,m,sqrtn,a[30],b[30],f[100000],ans;

int power(int x,int k)
{
    int ret=1;
    for (; k; k>>=1,x=LL(x)*x%p)
        if (k&1)
            ret=LL(ret)*x%p;
    return ret;
}

void get()
{
    int x=n;
    for (int i=2; i*i<=x; ++i)
        if (!(x%i))
            for (a[++m]=i; !(x%i); x/=i,++b[m]);
    if (x>1)
        a[++m]=x,b[m]=1;
}

void dfs(int i,int x,int y)
{
    if (i>m)
    {
        if (x==y)
        {
            (f[id(x)]+=power(k,(x+1)/2))%=p;
            ans=(ans+LL(x&1?x:x/2)*f[id(x)])%p;
        }
        else
            (f[id(y)]+=p-f[id(x)])%=p;
        return;
    }
    int t=y;
    repu(j,0,b[i])
    {
        if (j)
            x*=a[i],t*=a[i];
        y=t;
        repu(k,j,b[i])
        {
            if (k>j)
                y*=a[i];
            dfs(i+1,x,y);
        }
    }
}

int main()
{
    scanf("%d%d",&n,&k),sqrtn=sqrt(n);
    get(),dfs(1,1,1);
    printf("%d\n",ans);
    return 0;
}