← 返回题目列表

Codeforces · 1569/C

C. 评审团会议

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

$$$n$$$人聚集在一起召开即将举行的比赛的评审团会议,第$$$i$$$评审团成员提出了$$$a_i$$$任务,他们想与彼此分享。

首先,评审团决定在描述任务时遵循的顺序。假设这是从 $$$1$$$ 到 $$$n$$$ 的数字的排列 $$$p$$$(大小为 $$$n$$$ 的数组,其中从 $$$1$$$ 到 $$$n$$$ 的每个整数只出现一次)。

那么讨论如下:

- 如果陪审团成员 $$$p_1$$$ 还有一些任务需要讲述,那么他们会将一项任务告诉其他人。否则,它们将被跳过。
- 如果陪审团成员 $$$p_2$$$ 还有一些任务需要讲述,那么他们会将一项任务告诉其他人。否则,它们将被跳过。
- ...
- 如果陪审团成员 $$$p_n$$$ 还有一些任务需要讲述,那么他们会将一项任务告诉其他人。否则,它们将被跳过。
- 如果仍有成员留下任务,则该过程从头开始重复。否则,讨论结束。

如果没有评审团成员连续讲述两个或多个他们自己的任务,则排列 $$$p$$$ 是很好的。

计算好排列的数量。答案可能非常大,所以打印它对 $$$998\,244\,353$$$ 取模。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 陪审团成员的数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) - 第 $$$i$$$ 陪审团成员提出的问题数量。

所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数 - 良好排列的数量,以 $$$998\,244\,353$$$ 为模。

示例

输入 #1

4
2
1 2
3
5 5 5
4
1 3 3 7
6
3 4 2 1 3 3

输出 #1

1
6
0
540

注意

示例中第一个测试用例的说明:

有两种可能的排列,$$$p = [1, 2]$$$ 和 $$$p = [2, 1]$$$。对于$$$p = [1, 2]$$$,过程如下:

1.第一位评委讲述一个任务;
2.第二位评委讲述任务;
3. 第一个评审团成员没有任何任务要讲述,因此被跳过;
4. 第二位评委讲述一项任务。

所以,第二个评审团成员连续(连续)讲述了两个任务,所以排列并不好。

对于 $$$p = [2, 1]$$$,过程如下:

1.第二位评委讲述任务;
2.第一位评委讲述任务;
3. 第二位评委讲述一项任务。

所以,这个排列很好。