問題文

長さ $N$ の正整数列 $A$ が与えられます。 長さ $N$ の整数列 $B$ について、スコア $f(B)$ は次のように定義されます。

• 次の操作を $1$ 回以下行う
  • 整数 $i \ (1 \le i < N)$ を選択し、 $B_i$ と $B_{i+1}$ の値を交換する
• 適切に操作をしたとき、 $A_i < B_i$ を満たす $i\ (1\le i \le N)$ の個数の最大値が $f(B)$ となる

全ての要素が $1$ 以上 $M$ 以下の長さ $N$ の整数列 $B$ として考えられるものは $M^N$ 通りありますが、それら全てについてスコア $f(B)$ を求め、その総和を $998244353$ で割ったあまりを求めてください。

制約

• $2 \le N \le 2 \times 10^5$
• $1 \le M \le 10^9$
• $1 \le A_i \le M\ (1 \le i \le N)$
• 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$
$A_1$ $A_2$ $\ldots$ $A_N$ 

出力

答えを出力せよ。

サンプル

3 4
1 2 3

117

9 10
9 9 8 2 4 4 3 5 3

871841628

10 100
82 28 26 33 15 28 21 56 32 48

2025