题目描述

Bob 对排列有严格的要求。

对于一个排列 $p_i$，Bob 称一个元素 $p_i$ 是前缀最值，当且仅当对于所有的 $j<i$，$p_j$ 都小于 $p_i$。Bob 定义 $f(p_i)$ 为 $p_i$ 中所有前缀最值组成的序列。例如 $f([1,3,2,4]) = [1,3,4]$，$f([4,3,2,1]) = [4]$。

Bob 现在有一个序列 $\{a_i\}$，他想知道，有多少个 $1 \sim n$ 的排列 $p_i$ 使得 $f(p_i) = a_i$。由于这样的排列可能很多，你只需要输出答案对 $998244353$ 取模的值。

输入格式

第一行一个整数 $T$ 表示询问组数。

接下来 $T$ 组询问：

每组询问第一行两个整数 $n,k$，代表 $\{p_i\}$ 的长度和 $\{a_i\}$ 的长度。

接下来一行 $k$ 个整数，第 $i$ 个整数代表 $a_i$。

输出格式

共 $T$ 行，每行一个整数，代表该组询问满足条件的排列数量对 $998244353$ 取模的值。

3
3 1
3
4 2
2 4
5 3
1 3 5

2
3
3

数据范围

对于 $30\%$ 的数据，$1 \le k \le n \le 9$，$1 \le \sum n \le 9$； 对于 $60\%$ 的数据，$1 \le k \le n \le 10^3$，$1 \le \sum n \le 10^3$； 对于 $100\%$ 的数据，$1 \le T \le 10^5$，$1 \le k \le n \le 2 \cdot 10^5$，$1 \le \sum n \le 2 \cdot 10^5$，$1 \le a_1 < a_2 < \ldots < a_k = n$。