AT_arc112_e.[ARC112E] Cigar Box

对于数列 $(1,2,\dots,n)$，经过恰好 $m$ 次如下操作后，变成了 $(a_1,\dots,a_n)$。

• 选择一个项并将其删除。然后，将被删除的项添加到数列的开头或末尾。

请你求出，作为 $m$ 次操作序列可能的方案数，模 $998244353$ 的余数。

这里，两个操作序列相同，当且仅当“每一步所选的项和添加的位置都相同”。

输入以如下格式从标准输入给出。

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

输出作为操作序列可能的方案数，模 $998244353$ 的余数。

限制条件

• $2 \leq n \leq 3000$
• $1 \leq m \leq 3000$
• $a_1,\dots,a_n$ 是 $1,\dots,n$ 的一个排列

样例解释 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

在 $4$ 种操作中，有 $2$ 种操作不会改变数列，另外 $2$ 种操作会交换 $2$ 个元素。因此，所有操作序列中有一半（即 $4^m/2 = 2^{31} = 2147483648$）是满足条件的。于是，$2147483648$ 除以 $998244353$ 的余数 $150994942$ 就是答案。

由 ChatGPT 4.1 翻译