对于长度为$$$n$$$的排列$$$p_1, p_2, \ldots, p_n$$$,可以通过以下着色过程得到对应的着色序列$$$s$$$:
- 最初,有 $$$n$$$ 个白色单元格,从左到右索引为从 $$$1$$$ 到 $$$n$$$。在第二个$$$0$$$时,每个单元格的分数为$$$0$$$。
- 在第二个 $$$i$$$ ($$$1 \le i \le n$$$),
- 如果$$$i \gt 1$$$,找到距离单元格$$$p_i$$$最近的黑色单元格,并将该单元格的分数增加$$$1$$$。如果有多个最近的黑色单元格,请选择索引最低的单元格。仅当单元格 $$$y$$$ 为黑色且不存在满足 $$$|x-z| 的黑色单元格 $$$z$$$ 时,单元格 $$$y$$$ 被称为距单元格 $$$x$$$ 最近的黑色单元格。 \lt |x-y|$$$。
- 将单元格 $$$p_i$$$ 设置为黑色。
将所有单元格着色为黑色后,将$$$s_i$$$表示为单元格$$$i$$$的得分($$$1 \le i \le n$$$),我们得到着色序列$$$s$$$。
您可能需要阅读注释以更好地理解。
给你一个不完整的着色序列$$$s$$$,其中一些$$$s_i$$$已经固定,而另一些尚未确定。计算有多少种不同的排列 $$$p$$$ 可以产生这个着色序列。由于答案可能很大,因此您需要对 $$$998\,244\,353$$$ 进行模输出。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^3$$$)。测试用例的描述如下。
对于每个测试用例,第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 100$$$)。
第二行包含 $$$n$$$ 整数 $$$s_1, s_2, \ldots, s_n$$$ ($$$-1 \leq s_i \leq n-1$$$)。这里$$$s_i=-1$$$表示$$$s_i$$$尚未确定。 $$$s_i \neq -1$$$ 表示 $$$s_i$$$ 已经被修复。
保证所有测试用例的$$$n^2$$$总和不超过$$$10^4$$$。
输出
对于每个测试用例,输出可以产生着色序列的不同排列 $$$p_1, p_2, \ldots, p_n$$$ 的总和,模 $$$998\,244\,353$$$。
示例
输入复制
93-1 -1 13-1 -1 -14-1 2 -1 04-1 0 1 -15-1 3 -1 0 -154 4 4 4 451 0 1 2 06-1 1 -1 -1 3 013-1 -1 -1 -1 -1 -1 2 -1 -1 -1 -1 -1 -1
输出复制
2 6 4 3 8 0 4 10 867303072
注意
在第一个测试用例中, $$$p=[3,1,2]$$$ 和 $$$p=[3,2,1]$$$ 可以产生着色序列 $$$s=[-1,-1,1]$$$。
对于$$$p=[3,1,2]$$$,着色过程如下图所示。
![]() | ![]() | ![]() | ![]() |
对于$$$p=[3,2,1]$$$,着色过程如下图所示。
![]() | ![]() | ![]() | ![]() |





