题目描述

我们对序列$(1,2,\\dots,n)$进行了以下操作$m$次，结果得到了$(a_1,\\dots ,a_n)$。

• 删除一个元素。然后，将删除的元素添加到序列的开头或结尾。

计算进行这$m$次操作的可能序列的数量，取模为$998244353$。

在这里，当在每个操作中选择相同的元素并将其添加到相同的位置时，认为两个操作序列相同。

约束条件

• $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$

输出

打印进行这$m$次操作的可能序列的数量，取模为$998244353$。

示例输入 1

5 2
1 2 4 5 3

示例输出 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)$。

示例输入 2

2 16
1 2

示例输出 2

150994942

四种操作中的两种对序列没有影响，其他两种操作会交换两个元素。从这个事实我们知道，有$4^m/2 = 2^{31} = 2147483648$种我们想要计数的操作序列 - 所有可能序列的一半。因此，答案是$2147483648$取模$998244353$，即$150994942$。

示例输入 3

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

示例输出 3

129989699