問題文

1, 2, \dots , m からなる数列 (v_1, v_2, \dots, v_k) と 関数 f\colon \{1,\dots,m\} \to \{1,\dots,m\} について、 f が以下の条件を満たすとき、f が (v_1, v_2, \dots, v_k) を逆にする と言います。

• 数列 (f(v_1), f(v_2), \dots, f(v_k)) はもとの数列をひっくり返した数列 (v_k, v_{k-1}, \dots, v_1) と一致する

1, 2, \dots ,m からなる数列 (a_1, a_2, \dots, a_n) が与えられます。 この数列の空でない連続部分列は \frac{n(n+1)}{2} 通りありますが、 逆にする関数が何通り存在するかをこれら全てに対して数え上げて、その総和を 998244353 で割ったあまりを求めてください。

注意

• 関数 f と g について f(i)\neq g(i) となる i\in \{1,\dots,m\} が存在するとき f と g が異なる関数であるとみなす

制約

• 1\leq n, m \leq 3\times 10^5
• 各 i=1, 2, \dots, n について 1\leq a_i \leq m
• 入力はすべて整数である

入力例 1

3 3
1 1 2

出力例 1

39

数列 (1, 1, 2) の連続部分列は (1) と (1, 1) と (1, 1, 2) と (1) と (1, 2) と (2) です。

• 関数 f が数列 (1) を逆にするための必要十分条件は f(1)=1 で、この条件を満たす \{1, 2, 3\} 上の関数は 9 通りあります。
• 関数 f が数列 (1, 1) を逆にするための必要十分条件は f(1)=1 で、この条件を満たす \{1, 2, 3\} 上の関数は 9 通りあります。
• 関数 f が数列 (1, 1, 2) を逆にするための必要十分条件は f(1)=2 かつ f(1)=1 かつ f(2)=1 で、この条件を満たす関数はありません。
• 関数 f が数列 (1, 2) を逆にするための必要十分条件は f(1)=2 かつ f(2)=1 で、この条件を満たす \{1, 2, 3\} 上の関数は 3 通りあります。
• 関数 f が数列 (2) を逆にするための必要十分条件は f(2)=2 で、この条件を満たす \{1, 2, 3\} 上の関数は 9 通りあります。

よって、答えは 9 + 9 + 0 + 9 + 3 + 9 = 39 です。

入力例 2

20 20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

出力例 2

326566600

998244353 で割ったあまりを取るのを忘れないようにしてください。

入力例 3

46 128
109 98 111 106 103 46 51 46 58 50 49 51 106 102 108 108 106 111 48 116 117 116 102 117 111 112 100 48 113 107 47 115 102 101 112 100 117 98 48 48 59 116 113 117 117 105

出力例 3

249064602