配点 : $700$ 点

問題文

数列 $(1,2,\dots,n)$ に対して、以下の操作をちょうど $m$ 回繰り返したところ、$(a_1,\dots ,a_n)$ になりました。

• 項を $1$ つ選んで消す。その後、消した項を数列の先頭か末尾に付け加える。

$m$ 回の操作列としてありうるものの数を $998244353$ で割ったあまりを求めてください。

ただし、$2$ つの操作列が同じであるとは、「どの操作についても、選んだ項と付け加えた位置がどちらも等しいこと」とします。

制約

• $2\le n \le 3000$
• $1\le m \le 3000$
• $a_1,\dots ,a_n$ は $1,\dots,n$ の順列

入力

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

$n$ $m$

$a_1$ $\dots$ $a_n$

出力

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

5 2
1 2 4 5 3

5

以下の $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)$ となる。

2 16
1 2

150994942

$4$ 種類の操作のうち、$2$ 種類では数列が全く変わらず、もう $2$ 種類では $2$ 項が入れ替わります。 このことから、全ての操作列のうち半分である $4^m/2 = 2^{31} = 2147483648$ が求める操作列の数であることが示せます。 よって、$2147483648$ を $998244353$ で割ったあまりである $150994942$ が答えです。

10 3000
3 7 10 1 9 5 4 8 6 2

129989699