AT_arc112_e [ARC112E] Cigar Box

[problemUrl]: https://atcoder.jp/contests/arc112/tasks/arc112_e 数列 $ (1,2,\dots,n) $ に対して、以下の操作をちょうど $ m $ 回繰り返したところ、$ (a_1,\dots\ ,a_n) $ になりました。 - 項を $ 1 $ つ選んで消す。その後、消した項を数列の先頭か末尾に付け加える。 $ m $ 回の操作列としてありうるものの数を $ 998244353 $ で割ったあまりを求めてください。 ただし、$ 2 $ つの操作列が同じであるとは、「どの操作についても、選んだ項と付け加えた位置がどちらも等しいこと」とします。

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

操作列としてありうるものの数を $ 998244353 $ で割ったあまりを出力せよ。

### 制約 - $ 2\le\ n\ \le\ 3000 $ - $ 1\le\ m\ \le\ 3000 $ - $ a_1,\dots\ ,a_n $ は $ 1,\dots,n $ の順列 ### Sample Explanation 1 以下の $ 5 $ 通りの操作列がありえます。 - $ 1 $ を消して先頭に付け加える。数列は $ (1,2,3,4,5) $ となる。その後、$ 3 $ を消して末尾に付け加える。数列は $ (1,2,4,5,3) $ となる。 - $ 3 $ を消して先頭に付け加える。数列は $ (3,1,2,4,5) $ となる。その後、$ 3 $ を消して末尾に付け加える。数列は $ (1,2,4,5,3) $ となる。 - $ 3 $ を消して末尾に付け加える。数列は $ (1,2,4,5,3) $ となる。その後、$ 1 $ を消して先頭に付け加える。数列は $ (1,2,4,5,3) $ となる。 - $ 3 $ を消して末尾に付け加える。数列は $ (1,2,4,5,3) $ となる。その後、$ 3 $ を消して末尾に付け加える。数列は $ (1,2,4,5,3) $ となる。 - $ 5 $ を消して末尾に付け加える。数列は $ (1,2,3,4,5) $ となる。その後、$ 3 $ を消して末尾に付け加える。数列は $ (1,2,4,5,3) $ となる。 ### Sample Explanation 2 $ 4 $ 種類の操作のうち、$ 2 $ 種類では数列が全く変わらず、もう $ 2 $ 種類では $ 2 $ 項が入れ替わります。 このことから、全ての操作列のうち半分である $ 4^m/2\ =\ 2^{31}\ =\ 2147483648 $ が求める操作列の数であることが示せます。 よって、$ 2147483648 $ を $ 998244353 $ で割ったあまりである $ 150994942 $ が答えです。