D-小苯的排列计数_牛客周赛 Round 82

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

$\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\}$ 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：
第一行输入一个整数  代表排列中的元素数量。
第二行输入  个整数  代表排列的每一个前缀的最小值。

除此之外，保证单个测试文件的  之和不超过 。

输出描述:

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

示例1

输入

复制

4
3
3 2 1
4
2 2 1 1
2
2 2
7
6 2 2 1 1 1 1

输出

复制

说明

对于第一组测试数据，符合条件的排列仅为 。

对于第二组测试数据，需要满足：，有且仅有排列  和  满足条件。

对于第三组测试数据，长度为  的排列有且仅有  和  两种。而前者的前缀最小值依次为 ，后者的前缀最小值依次为 ，均与输入的  数组不符，因此不存在符合条件的排列。