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<bits/stdc++.h>
#define L long long
using namespace std;
const int q=1000000007;
int n,m,x[100010],t,f[100010],p;
inline int power(int a,int b)
{
	if(!b)
	  return 1;
	int c=power(a,b>>1);
	c=(L)c*c%q;
	if(b&1)
	  c=(L)c*a%q;
	return c;
}
int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	int i,j;
	scanf("%d%d",&n,&m);
	for(i=1;i*i<=n;i++)
	  if(n%i==0)
	    {
		 x[++t]=i;
		 if(n/i!=i)
		   x[++t]=n/i;
		}
	sort(x+1,x+t+1);
	for(i=1;i<=t;i++)
	  {
	   f[i]=power(m,(x[i]+1)/2);
	   for(j=1;j<i;j++)
	     if(x[i]%x[j]==0)
	       f[i]=(f[i]-f[j])%q;
	   p=(p+(L)f[i]*((x[i]&1)?x[i]:(x[i]/2)))%q;
	  }
	p=(p+q)%q;
	printf("%d\n",p);
	return 0;
}
