#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define mod 998244353
#define sz(x) (int)((x).size())
#define int ll
//#define N
using namespace std;
const int N=10000005;
int fac[N],mul[N],inv[N],f[N];
int n,m;

inline ll quickPower(ll x,ll y)
{
	ll res=1;
	while (y)
	{
		if (y&1) res=res*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return res;
}
inline int C(int x,int y)
{
	if (x<y||y<0) return 0;
	return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
int way(int x,int y)
{
	return C(x+y,y);
}
int way_(int x,int y)
{
	return (way(x,y)-way(y-1,x+1)+mod)%mod;
}

int h[N],hh[N];
int re[N];
void build_re(int nn)
{
	int x,now=nn>>1,len=0;
	while(now)
	  len++,now>>=1;
	for(int i=0;i<nn;i++)
	{
		x=i;now=0;
		for(int j=0;j<len;j++)
		  now=(now<<1)|(x&1),x>>=1;
		re[i]=now;
	}
}

//void FFT(complex a[],int len,int opt)
//{
//	for(int i=0;i<len;i++)
//	  if(i<re[i])
//	    swap(a[i],a[re[i]]);
//	complex wn,w,x;
//	for(int i=2;i<=len;i<<=1)
//	  for(int j=(wn=(complex){cos(pi*2/i),opt*sin(pi*2/i)},0);j<len;j+=i)
//	  	for(int k=(w=(complex){1,0},0);k<i>>1;k++,w=w*wn)
//	  	  x=w*a[j+k+(i>>1)],a[j+k+(i>>1)]=a[j+k]-x,a[j+k]=a[j+k]+x;
//	if(opt==-1)
//	  for(int i=0;i<len;i++)
//	    a[i]=a[i]/len;
//}
void NTT(long long a[],int len,int opt)
{
	for(int i=0;i<len;i++)
	  if(i<re[i])
	    swap(a[i],a[re[i]]);
	long long wn,w,x;
	for(int i=2;i<=len;i<<=1)
	  for(int j=(wn=quickPower(3,(mod-1)/i),(opt==-1?wn=quickPower(wn,mod-2):0),0);j<len;j+=i)
	    for(int k=(w=1,0);k<i>>1;k++,w=w*wn%mod)
	      x=a[j+k+(i>>1)]*w%mod,a[j+k+(i>>1)]=(a[j+k]-x+mod)%mod,a[j+k]=(a[j+k]+x)%mod;
	if(opt==-1)
	{
		long long inv=quickPower(len,mod-2);
		for(int i=0;i<len;i++)
		  a[i]=a[i]*inv%mod;
	}
}
void poly_inv(long long a[],long long tar[],int len)
{
	static long long now[N],ret[N];
	memset(now,0,sizeof(long long)*len);memset(ret,0,sizeof(long long)*len);
	ret[0]=quickPower(a[0],mod-2);
	for(int i=2;i<=len;i<<=1)
	{
		build_re(i<<1);
		memcpy(now,a,sizeof(long long)*i);
		NTT(ret,i<<1,1);NTT(now,i<<1,1);
		for(int j=0;j<i<<1;j++)
		  ret[j]=ret[j]*(2LL-now[j]*ret[j]%mod+mod)%mod;
		NTT(ret,i<<1,-1);
		memset(ret+i,0,sizeof(long long)*i);
	}
	memcpy(tar,ret,sizeof(long long)*len);
}
void BellaKira()
{
	cin>>n>>m;
	n*=2;
	poly g;
	for (int i=1;i<=n;i++)	
		mul[__gcd(i,n)]++;
	if (m==1)
	{
		cout<<1<<'\n';
		return;
	}
	hh[0]=1;
	for (int i=1;i<=n/2;i++) 
		hh[i]=(mod-way_(i-1,i-1)*quickPower(m-1,i-1)%mod*m%mod)%mod;
	int Len=1;
	while(Len<=n/2+1)
	  Len<<=1;
	poly_inv(hh,h,Len);
	// for (int i=0;i<=n;i++) cout<<h[i]<<" ";
	// cout<<endl;
	int ans=0;
	for (int i=1;i<=n;i++)
	{
		if (n%i==0)
		{
			if (i%2==0)
			{
				if (m==1) f[i]=1;
				else
					f[i]=h[i/2];
			} else
			{
				if (m==1) f[i]=1;
				else
				for (int j=0;j<=i/2;j++)
				{	
					f[i]=(f[i]+way(j,i-j)*m%mod
					*quickPower(m-1,j)%mod)%mod;
				}
			}
			// cout<<i<<" "<<f[i]<<" "<<mul[i]<<" "<<way_(4,4)<<endl;
			ans=(ans+f[i]*mul[i]%mod)%mod;
		}
	}
	// cout<<ans<<'\n';
	cout<<ans*quickPower(n,mod-2)%mod<<'\n';
}
signed main()
{
	fac[0]=1;
	for (int i=1;i<N;i++)
		fac[i]=fac[i-1]*i%mod;
	inv[N-1]=quickPower(fac[N-1],mod-2);
	for (int i=N-1;i>=1;i--)
		inv[i-1]=inv[i]*i%mod;
	IOS;
	cin.tie(0);
	int T=1;
	while (T--)
	{
		BellaKira();
	}
}