一群 $$$n$$$ 人决定装饰圣诞树。他们有 $$$(n+1)$$$ 盒装饰品,编号从 $$$0$$$ 到 $$$n$$$。最初,第 $$$i$$$ 个盒子包含 $$$a_i$$$ 装饰品。
我们说大小为 $$$n$$$ 的排列 $$$p$$$ (大小为 $$$n$$$ 的数组,其中从 $$$1$$$ 到 $$$n$$$ 的每个数字恰好出现一次)是 公平 如果可以使用以下过程将所有装饰品挂在树上:
- 人$$$p_1$$$从盒子$$$0$$$或盒子$$$p_1$$$中取出装饰品,并将其挂在树上;
- 人$$$p_2$$$从盒子$$$0$$$或盒子$$$p_2$$$中取出装饰品,并将其挂在树上;
- 等等;
- 在 person $$$p_n$$$ 之后,接着 person $$$p_1$$$,并且重复该过程,直到所有装饰都在树上。
在此过程中,绝不能出现$$$i$$$需要挂装饰品,但盒子$$$0$$$和盒子$$$i$$$都是空的情况。如果这种情况无法避免,则排列是不公平的。然而,如果人们可以在每个步骤中选择从哪个盒子中进行装饰,从而不会出现这种情况,那么排列就是公平的。
你的任务是计算公平排列的数量。由于答案可能很大,因此输出它对 $$$998244353$$$ 取模。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 5000$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 50$$$)。
第二行包含 $$$(n+1)$$$ 整数 $$$a_0, a_1, \dots, a_n$$$ ($$$0 \le a_i \le 10^6$$$)。
输出
对于每个测试用例,打印一个整数 - 公平排列的数量,以 $$$998244353$$$ 为模。
示例
输入复制
431 2 1 031 0 2 012 546 1 4 2 1
输出复制
20112
注意
在第一个示例中,公平排列是 $$$[1, 2, 3]$$$ 和 $$$[1, 3, 2]$$$。
让我们仔细看看排列 $$$[1, 3, 2]$$$ 的圣诞树装饰:
- 此人$$$p_1=1$$$从盒子$$$1$$$上挂了一个装饰品;
- 此人$$$p_2=3$$$从盒子$$$0$$$上挂了一个装饰品;
- 此人$$$p_3=2$$$从盒子$$$2$$$上挂了一个装饰品;
- $$$p_1=1$$$ 人在盒子 $$$1$$$ 上悬挂了一件装饰品。
请注意,如果人 $$$p_1=1$$$ 在第一步中从盒子 $$$0$$$ 中取出装饰,那么人 $$$p_2=3$$$ 将无法执行下一步(因为 $$$0$$$ 和 $$$3$$$ 两个盒子都是空的)。然而,由于这种情况是可以避免的,因此排列是公平的。