首先考虑木棍问题。

注意到 $T+T=A+B+A+B=A+S+B$，所以 $S=B+A$。

故 $T$ 是 $S$ 的循环移位。

设 $S$ 的最小循环节长度为 $L$，则 $S$ 的本质不同循环移位个数为 $L$。

直接计算最小循环节长度恰好为 $L$ 的字符串个数 $f_L$ 不简单。

所以计算存在长度为 $L$ 循环节字符串个数 $g_L$。显然 $g_L=m^L[L \mid n]$。

接着考虑计算 $f_L$，显然若 $L \mid n$，则 $f_L=g_L - \sum_{d \mid L} f_d$。（可能存在长度比 $L$ 更小的循环移位）。

直接计算即可。

我写的 $O(\sqrt{n}+d(n)^2)$，显然这个做法随便爆，不管了。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=10000;
ll n,d[N];
int m,c,ans,f[N],p=998244353;
int ksm(int x,ll y){
	if(y==0) return 1; int z=ksm(x,y>>1);
	return z=1ll*z*z%p,y&1?1ll*z*x%p:z;
}
signed main(){
	cin>>n>>m;
	for(int i=1;1ll*i*i<=n;i++) if(n%i==0){
		d[++c]=i;
		if(i*i!=n) d[++c]=n/i;
	}
	sort(d+1,d+c+1);
	for(int i=1;i<=c;i++) f[i]=ksm(m,d[i]);
	for(int i=1;i<=c;i++) for(int j=i+1;j<=c;j++)
		if(d[j]%d[i]==0) f[j]=(f[j]-f[i]+p)%p;
	for(int i=1;i<=c;i++) ans=(ans+1ll*(d[i]%p)*(d[i]%p)%p*f[i]%p)%p;
	return cout<<ans<<'\n',0;
}