Description：

求出所有长度为 $n$ ，只包含前 $k$ 个字符的满足以下条件的字符串个数：

对于字符串 $A$ 和 $B$ ，存在 $C$ 使得 $A+C=C+B$

$1\le n \le 10^9,1\le k \le 26$

Solution：

$A$ 和 $B$ 必须是循环同构的，如果 $A$ 串的最小循环节长度为 $k$ ，那么最多只能有 $k$ 个 $B$ 。于是设 $f[i]$ 表示最小循环节长度为 $n$ 的第 $i$ 个约数时的方案数， $\begin{align}ans=\sum_{i|n}i\times f[i]\end{align}$ ，循环节长度为 $n$ 的第 $i$ 个约数的方案数是 $k^{fac[i]}$ ，然后再容斥掉 $fac[i]$ 的约数即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

typedef long long ll;

#define MOD 1000000007

ll n,k;

ll power(ll a,ll b)

{

	ll res = 1;

	while(b > 0)

	{

		if(b & 1)res = res * a % MOD;

		a = a * a % MOD;

		b = b >> 1;

	}

	return res;

}

#define MAXN 1000000

ll fac[MAXN],tot = 0,f[MAXN];

int main()

{

	scanf("%lld%lld",&n,&k);

	for(int i = 1;i * i <= n;++i)

	{

		if(n % i == 0)

		{

			fac[++tot] = i;

			if(i * i != n)

			{

				fac[++tot] = n / i;

			}

		}

	}

	sort(fac + 1,fac + 1 + tot);

	for(int i = 1;i <= tot;++i)

	{

		f[i] = power(k,fac[i]);

		for(int j = 1;j < i;++j)if(fac[i] % fac[j] == 0)f[i] = (f[i] - f[j] + MOD) % MOD;

	}

	ll ans = 0;

	for(int i = 1;i <= tot;++i)ans = (ans + fac[i] * f[i] % MOD) % MOD;

	cout << ans << endl;

	return 0;

}