题目描述

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

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

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

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

输入格式

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

$n$ $m$ $a_1$ $\dots$ $a_n$

输出格式

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

题目大意

给定序列 $1,2,\cdots,n$，要求进行 $m$ 次操作，将这个序列变为 $a_1,a_2,\cdots,a_n$，问有多少种不同的操作方案数？一次操作是指：将排列中的任意一个数移到第一个或移到最后一个。

数据范围

• $2\leqslant n\leqslant 3000$
• $1\leqslant m\leqslant 3000$

5 2
1 2 4 5 3

5

2 16
1 2

150994942

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

129989699

提示

制約

• $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$ が答えです。