有一个隐藏数组 $$$a$$$,大小为 $$$n$$$,仅由 $$$1$$$ 和 $$$-1$$$ 组成。令$$$p$$$ 为数组$$$a$$$ 的前缀和。更正式地说,$$$p$$$ 是一个长度为 $$$n$$$ 的数组,定义为 $$$p_i = a_1 + a_2 + \ldots + a_i$$$。之后,数组 $$$p$$$ 按非降序排序。例如,如果 $$$a = [1, -1, -1, 1, 1]$$$,则排序前 $$$p = [1, 0, -1, 0, 1]$$$,排序后 $$$p = [-1, 0, 0, 1, 1]$$$。
排序后得到前缀和数组 $$$p$$$,但你不知道数组 $$$a$$$ 是什么。您的任务是计算初始数组 $$$a$$$ 的数量,以便上述过程产生给定的排序前缀和数组 $$$p$$$。由于这个数字可能很大,因此您只需对 $$$998\,244\,353$$$ 求模即可。
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5000$$$) — 隐藏数组 $$$a$$$ 的大小。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$p_1, p_2, \ldots, p_n$$$ ($$$|p_i| \le n$$$) - $$$a$$$ 的 $$$n$$$ 前缀总和按非降序排序。
保证 $$$p_1 \le p_2 \le \ldots \le p_n$$$。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$5000$$$。
输出
对于每个测试用例,输出对 $$$998\,244\,353$$$ 取模的答案。
示例
输入 #1
5 1 0 1 1 3 -1 1 2 5 -1 0 0 1 1 5 -4 -3 -3 -2 -1
输出 #1
0 1 0 3 1
注意
在前两个测试用例中,$$$n = 1$$$ 唯一可能的数组 $$$a$$$ 是 $$$a = [1]$$$ 和 $$$a = [-1]$$$。它们各自的排序前缀和数组 $$$p$$$ 为 $$$p = [1]$$$ 和 $$$p = [-1]$$$。因此,没有数组 $$$a$$$ 可以生成排序后的前缀和数组 $$$p = [0]$$$,并且恰好存在 $$$1$$$ 数组 $$$a$$$ 可以生成排序后的前缀和数组 $$$p = [1]$$$。
在第三个测试用例中,可以证明不存在数组 $$$a$$$ 可以产生排序后的前缀和数组 $$$p = [-1, 1, 2]$$$。
在第四个测试用例中,可能产生排序前缀和数组 $$$p = [-1, 0, 0, 1, 1]$$$ 的 $$$3$$$ 可能数组 $$$a$$$ 是:
- $$$a = [1, -1, 1, -1, -1]$$$。排序前的前缀和数组为 $$$p = [1, 0, 1, 0, -1]$$$,排序后为 $$$p = [-1, 0, 0, 1, 1]$$$。
- $$$a = [1, -1, -1, 1, 1]$$$。排序前的前缀和数组为 $$$p = [1, 0, -1, 0, 1]$$$,排序后为 $$$p = [-1, 0, 0, 1, 1]$$$。
- $$$a = [-1, 1, 1, -1, 1]$$$。排序前的前缀和数组为 $$$p = [-1, 0, 1, 0, 1]$$$,排序后为 $$$p = [-1, 0, 0, 1, 1]$$$。
对于第五个测试用例,唯一可能产生排序前缀和数组 $$$p = [-4, -3, -3, -2, -1]$$$ 的数组 $$$a$$$ 是 $$$a = [-1, -1, -1, -1, 1]$$$。