这题一眼望过去，用不了什么现成的科技，最朴素的思路就是，考虑每个串会被算几次。

事实上，一个串会被算多次，也意味着有两个回文串互相循环同构。

循环同构也会出现所谓“重复”的情况，这与一个串的最小整周期有关。

如果一个回文串的最小整周期为 ，那么只有 个串是“可能有用的”

故我们先考虑一个周期内的问题。

回文串有两种： 和 ( 表示 的翻转， 表示一个字符)

对于 ，与其循环同构的回文串只有

对于 ，没有与其循环同构的回文串。（这就是我没有发现的地方）

所以如果 是偶数，一个回文串会带来 的贡献，否则带来 的贡献。

接下来考虑如何算周期为 的回文串个数。

先可以算周期是 约数的回文串个数，为 ，再用其约数的答案来减即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 6000,P = 1e9 + 7;
inline int qpow(int a,int b) { int res = 1;while(b) {if(b&1) res = 1ll * res * a % P;a = 1ll * a * a % P;b >>= 1;} return res;}
int factor[N],f[N],tot,n,k;
int main()
{
	scanf("%d%d",&n,&k);
	for(int i = 1;i * i <= n;i++)
	{
		if(n % i) continue;
		factor[++tot] = i;
		if(i * i != n) factor[++tot] = n / i;
	}
	sort(factor + 1,factor + tot + 1);
	int ans = 0;
	for(int i = 1;i <= tot;i++)
	{
		f[i] = qpow(k,(factor[i] + 1) >> 1);
		for(int j = 1;j < i;j++)
			if(factor[i] % factor[j] == 0) (f[i] += P - f[j]) %= P;
		ans = (ans + 1ll * ((factor[i] & 1) ? factor[i] : factor[i] / 2) * f[i] % P) % P;
	}
	cout << ans << endl;
	return 0;
}