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 <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define MOD 1000000007
using namespace std;
const int MAXN = 100005;
int fac[MAXN],n,f[MAXN],m;
inline int ksm(int x,int k)
{
  int ret=1;
  while(k){
    if(k&1)ret=(long long)ret*x%MOD;
    x=(long long)x*x%MOD;
    k>>=1;
  }
  return ret;
}
inline void sub(int &x,int a)
{
  x-=a;
  if(x<0)x+=MOD;
}
inline void add(int &x,int a)
{
  x+=a;
  if(x>=MOD)x-=MOD;
}
int main()
{
  scanf("%d%d",&n,&m);
  for(int i=1;i*i<=n;++i){
    if(n%i==0){
      fac[++fac[0]]=i;
      if(i*i!=n)fac[++fac[0]]=n/i;
    }
  }
  int ans=0;
  sort(fac+1,fac+fac[0]+1);
  for(int i=1;i<=fac[0];++i){
    f[i]=ksm(m,(fac[i]+1)>>1);
    for(int j=1;j<i;++j)
      if(fac[i]%fac[j]==0)sub(f[i],f[j]);
    if(fac[i]&1){
      add(ans,(long long)f[i]*fac[i]%MOD);      
    }else{
      add(ans,(long long)f[i]*fac[i]%MOD*500000004%MOD);
    }
  }
  cout<<ans<<endl;
  return 0;
}
