妙~.
千万不要因为数据大就害怕,得学会冷静分析...
对于这题而言,我们要知道一件事,就是回文串和循环节之间的一个关系.
首先回文串一定可以写成循环节的整数倍的形式).然后我们还得考虑一个移动过程,什么时候会重复.
这里的话要分奇偶了.
对于奇字符串而言:abaaba,假设循环节长度是len,那么移动len的长度后就会重复.
对于偶字符串而言:abbaabba,假设循环节长度是len,那么移动len/2的长度后就会重复.
循环节也必定是回文串.
所以啊,我们先枚举下n的所有因子ai,也就是循环节的长度,对于每个循环节的长度len,我们都可以直接算出来值k^((ai+1)/2),然后考虑去重就是循环节是aj且ai%aj==0的fj是已经计算过的.然后对于循环节是奇数的乘以len,偶数乘以len/2.ans+=f[i]即可!
ac代码如下:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const ll N=3000;
ll w[N],f[N];
ll qp(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }return res;
}

int main()
{
    ll n,k,id=0;
    scanf("%lld%lld",&n,&k);
    w[++id]=1,w[++id]=n;
    for(ll i=2;i<=n/i;i++)
    {
        if(n%i==0)
        {
            if(i!=n/i)   w[++id]=i,w[++id]=n/i;
            else         w[++id]=i;
        }
    }sort(w+1,w+1+id);
    ll ans=0;
    for(ll i=1;i<=id;i++)
    {
        f[i]=qp(k,(w[i]+1)/2);
        for(ll j=1;j<i;j++)
            if(w[i]%w[j]==0)    f[i]=(f[i]-f[j]+mod)%mod;
        if(w[i]&1)  ans=(ans+w[i]*f[i])%mod;
        else        ans=(ans+w[i]*f[i]/2)%mod;
    }
    printf("%lld\n",ans);
    return 0;
}