← 返回题目列表

Codeforces · 2182/D

D. 圣诞树装饰

中文机器翻译题面 查看原题

一群 $$$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$$$ 为模。

示例

输入
复制

4
3
1 2 1 0
3
1 0 2 0
1
2 5
4
6 1 4 2 1

输出
复制

2
0
1
12

注意

在第一个示例中,公平排列是 $$$[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$$$ 两个盒子都是空的)。然而,由于这种情况是可以避免的,因此排列是公平的。