問題文

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

• a の長さ 2 以上の連続部分列であって、回文であるようなものが存在しない。

制約

• 2 \le N \le 10^{12}
• 1 \le M \le 10^{12}
• 入力は全て整数

入力例 1

2 2

出力例 1

2

a=(1,2),(2,1) の時条件を満たします。

入力例 2

3 3

出力例 2

6

入力例 3

314 159

出力例 3

809839613

998244353 で割った余りを求めることをお忘れなく。

原案: turtle0123__