题目描述

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

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

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

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

输入格式

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

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

输出格式

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

样例 1

输入

5 2
1 2 4 5 3

输出

5

样例 2

输入

2 16
1 2

输出

150994942

样例 3

输入

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

输出

129989699

说明/提示

限制条件

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