题解：
首先看n是偶数的
那么就是不需要满足对面这个性质的
这样就可以dp了 f[i][0/1]表示dp到第i位，当前数等于或不等于第一位的方案数
然后显然可以用矩阵优化
再考虑n为奇数
用一样的思路，把环切成两半，先确定两个对应位置的值，再进行dp
f[i][0/1/2][0/1/2]表示dp到i位，下面这个数等不等于上面第一个，等不等于下面第一个（同理上面）
发现这个可以dp，依旧用矩阵优化一波
转移方程稍微有点复杂，有个对拍就轻松多了
另外注意f不能表示成f[i][0/1][0/1]表示和不同侧的起始点
原因是这样转移的时候会出现问题，无法确定它旁边的点和同侧的起始点之间的颜色关系（非常的绕口）
注意别少取模
#include <bits/stdc++.h>
using namespace std;
#define ll long long
struct re{
ll a[][];
}aa;
ll a[][],n,m;
#define mo 998244353
re XX(re x,re y)
{
re tmp;
memset(tmp.a,,sizeof(tmp.a));
for (ll i=;i<=;i++)
for (ll j=;j<=;j++)
for (ll k=;k<=;k++)
tmp.a[i][k]+=x.a[i][j]*y.a[j][k],
tmp.a[i][k]%=mo;
return tmp;
}
re fast_pow(ll x)
{
if (x==) return(aa);
re b=fast_pow(x/);
b=XX(b,b);
if (x%==) b=XX(b,aa);
return (b);
}
int main()
{
freopen("noip.in","r",stdin);
freopen("noip.out","w",stdout);
cin>>n>>m;
if (n%==)
{
a[][]=(m-)*(m-)+(m-);
a[][]=a[][]=a[][]=a[][]=(m-)*(m-)+(m-);
a[][]=a[][]=(m-)*(m-);
a[][]=a[][]=m-;
a[][]=a[][]=a[][]=m-;
a[][]=a[][]=m-;
a[][]=a[][]=a[][]=m-;
a[][]=a[][]=m-;
a[][]=a[][]=a[][]=m-;
a[][]=a[][]=m-;
a[][]=a[][]=a[][]=m-;
a[][]=a[][]=a[][]=a[][]=;
a[][]=a[][]=a[][]=a[][]=;
for (ll i=;i<=;i++)
for (ll i=;i<=;i++)
for (ll j=;j<=;j++)
aa.a[i][j]=max(*1ll,a[i][j]%mo);
/* for (ll i=1;i<=8;i++)
{
for (ll j=1;j<=8;j++)
cout<<aa.a[i][j]<<" ";
cout<<endl;
}
cout<<endl<<endl;*/
re x=fast_pow(n/-);
/* for (ll i=1;i<=8;i++)
{
for (ll j=1;j<=8;j++)
cout<<x.a[i][j]<<" ";
cout<<endl;
}*/
ll ans=x.a[][]+x.a[][]+x.a[][]+x.a[][];
ans=(ans*m)%mo*(m-);
ans=(ans%mo+mo)%mo;
cout<<ans;
}
return ;
}