统计前缀

• 时间限制：1 秒
• 内存限制：256 MiB

题目描述

有一个长度为 $n$ 的隐藏数组 $a$，其中每个元素均为 $1$ 或 $-1$。定义它的前缀和

$$q_i=a_1+a_2+\cdots+a_i\qquad(1\le i\le n).$$

随后，将 $q_1,q_2,\ldots,q_n$ 按非递减顺序排序。现在给定排序后的数组 $p$，求有多少个隐藏数组 $a$ 会得到它。答案对 $998244353$ 取模。

输入格式

第一行一个整数 $t$，表示测试用例数。

每个测试用例的第一行一个整数 $n$，第二行 $n$ 个整数 $p_1,p_2,\ldots,p_n$。

保证 $p_1\le p_2\le\cdots\le p_n$。

输出格式

对每个测试用例输出一行一个整数，表示答案对 $998244353$ 取模后的结果。

样例输入

5
1
0
1
1
3
-1 1 2
5
-1 0 0 1 1
5
-4 -3 -3 -2 -1

样例输出

0
1
0
3
1

样例解释

第四个测试用例中，三个可行的隐藏数组分别为

$$[1,-1,1,-1,-1],\quad[1,-1,-1,1,1],\quad[-1,1,1,-1,1].$$

数据范围

$1\le t\le1000$，$1\le n\le5000$，$|p_i|\le n$；所有测试用例的 $n$ 之和不超过 $5000$。

子任务编号	分值	特殊限制
1	20	每个 $n\le18$，且 $\sum n\le90$
2	40	$p_n-p_1\le20$
3		无特殊限制