\(M=1\) の場合は答えは \(0\) です。以下、 \(2 \le M\) とします。

回文に関する性質として、長さ \(3\) 以上の回文の両端を取り除いた数列も回文である、というものがあります。

これより、長さが \(2\) または \(3\) の回文が存在するかのみに着目すればよいです。

長さが \(2\) または \(3\) の数列が回文である必要十分条件は両端が等しいことですから、問題は次のように言い換えられます。

すべての要素が \(1\) 以上 \(M\) 以下である長さ \(N\) の正整数列 \(a\) であって、以下の条件を満たすものの個数を \(998244353\) で割った余りを求めてください。

• \(j-i \le 2\) を満たすすべての整数対 \((i,j) \ (i < j)\) について、 \(a_i \ne a_j\)

ここで、 \(\mathrm{dp}\) のように前の要素から条件を満たすように決めていくことを考えると、 \(a_1\) として考えられるものは \(M\) 通り、 \(a_2\) として考えられるものは \(M-1\) 通り、 \(a_i\ (3 \le i)\) として考えられるものは \(M-2\) 通りになります。

よって、答えは \(M(M-1)(M-2)^{N-2}\) と書け(便宜上 \(0^0=1\) としています)、これは繰り返し二乗法を用いれば時間計算量 \(O(\log N)\) で求まります。

実装例 (C++)

Bonus : \(a\) が円環の場合で解いてみましょう(\(500\) 点くらいだと思います)