AT_nikkei2019_2_final_h 逆にする関数

[problemUrl]: https://atcoder.jp/contests/nikkei2019-2-final/tasks/nikkei2019_2_final_h $ 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 $ で割ったあまりを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ n $ $ m $ $ a_1 $ $ a_2 $ $ \dots $ $ a_n $

数列の各連続部分列についての逆にする関数の数の合計を $ 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 $ - 入力はすべて整数である ### Sample Explanation 1 数列 $ (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 $ です。 ### Sample Explanation 2 $ 998244353 $ で割ったあまりを取るのを忘れないようにしてください。