U558844 小苯的排列计数

$\hspace{15pt}$小苯有一个长度为 n 的排列 $\{p_1,p_2,\dots,p_n\}$，但是，他忘记了每一个元素的具体数值，好在他记得排列的每一个前缀的最小值。具体地，我们使用数组 ${\rm prefix}$ 来表示排列的每一个前缀的最小值，其中，${\rm prefix}_i$ 代表排列中，前 $i$ 个元素的最小值。 $\hspace{15pt}$现在，根据这 $n$ 个前缀最小值，小苯想知道有多少个符合条件的排列 $p$，请你帮他数一数吧。特别地，若不存在符合要求的排列，则只需要输出 $0$ 即可。由于答案可能很大，请将答案对 $998\,244\,353$ 取模后输出。 $\hspace{15pt}$长度为 $n$ 的排列是由 $1 \sim n$ 这 $n$ 个整数、按任意顺序组成的数组，其中每个整数恰好出现一次。例如，$\{2,3,1,5,4\}$ 是一个长度为 $5$ 的排列，而 $\{1,2,2\}$ 和 $\{1,3,4\}$ 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。

每个测试文件均包含多组测试数据。第一行输入一个整数 $T$ 代表数据组数，每组测试数据描述如下： $\hspace{15pt}$第一行输入一个整数 $n$ 代表排列中的元素数量。 $\hspace{15pt}$第二行输入 $n$ 个整数 ${\rm prefix}_1,{\rm prefix}_2,\dots,{\rm prefix}_n$ 代表排列的每一个前缀的最小值。

$\hspace{15pt}$对于每一组测试数据，新起一行。输出一个整数，代表符合条件的排列的数量。特别地，若不存在符合要求的排列，则只需要输出 $0$ 即可。由于答案可能很大，请将答案对 $998\,244\,353$ 取模后输出。

$\hspace{15pt}$对于第一组测试数据，符合条件的排列仅为 $\{3,2,1\}$。 $\hspace{15pt}$对于第二组测试数据，需要满足：$\begin{cases}{\rm prefix}_1 & = & \min\{p_1\} & = & 2 \\{\rm prefix}_2 & = & \min\{p_1,p_2\} & = & 2 \\{\rm prefix}_3 & = & \min\{p_1,p_2,p_3\} & = & 1 \\{\rm prefix}_4 & = & \min\{p_1,p_2,p_3,p_4\} & = & 1\end{cases}$ $\hspace{15pt}$有且仅有排列 $\{2,4,1,3\}$ 和 $\{2,3,1,4\}$ 满足条件。 $\hspace{15pt}$对于第三组测试数据，长度为 $2$ 的排列有且仅有 $\{1,2\}$ 和 $\{2,1\}$ 两种。而前者的前缀最小值依次为 $\{1,1\}$，后者的前缀最小值依次为 $\{2,1\}$，均与输入的 ${\rm prefix}$ 数组不符，因此不存在符合条件的排列。 【**数据范围**】 对于 $10\%$ 的数据有：$T=1, 1 \leq n \leq 10$。 对于所有的测试数据有：$1\leq T\leq 10^3, 1 \leq n \leq 2 \times 10^5, 1 \leq a_i \leq n$。除此之外，保证单个测试文件的 $n$ 之和不超过 $3 \times 10^5。$