给定一个大小为 $$$n$$$ 的循环数组 $$$a$$$,其中 $$$a_i$$$ 是 $$$a$$$ 在第 $$$i$$$ 位置的值,可能存在重复值。让我们定义 $$$a$$$ 的排列等于 $$$a$$$ 的另一个排列,当且仅当它们的值对于每个位置 $$$i$$$ 相同,或者我们可以通过执行一些循环旋转将它们相互转换。让我们将循环数组 $$$b$$$ 的分量数量定义为图中连通分量的数量,其中顶点是 $$$b$$$ 的位置,并且我们在 $$$b$$$ 的每对相邻位置之间添加一条具有相等值的边(请注意,在循环数组中,第一个位置和最后一个位置也是相邻的)。
如果我们在 $$$a$$$ 的所有不同排列的集合上等概率地选择它,则求 $$$a$$$ 排列的分量的期望值。
输入
输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^5$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^6$$$) — 循环数组 $$$a$$$ 的大小。
每个测试用例的第二行包含 $$$n$$$ 个整数,其中第 $$$i$$$ 是值 $$$a_i$$$ ($$$1 \le a_i \le n$$$)。
保证所有测试用例的$$$n$$$总和不超过$$$10^6$$$。
保证$$$a$$$的不同排列总数不能被$$$M$$$整除
输出
对于每个测试用例,打印一个整数 - 如果我们在 $$$a$$$ 的所有不同排列的集合上以 $$$a$$$ 模 $$$998\,244\,353$$$ 为模,则 $$$a$$$ 排列的分量的期望值。
正式地,让 $$$M = 998\,244\,353$$$。可以证明,答案可以表示为不可约分数 $$$\frac{p}{q}$$$,其中 $$$p$$$ 和 $$$q$$$ 是整数,$$$q \not \equiv 0 \pmod{M}$$$。输出等于 $$$p \cdot q^{-1} \bmod M$$$ 的整数。换句话说,输出一个整数$$$x$$$,使得$$$0 \le x < M$$$ 且$$$x \cdot q \equiv p \pmod{M}$$$。
示例
输入 #1
5 4 1 1 1 1 4 1 1 2 1 4 1 2 1 2 5 4 3 2 5 1 12 1 3 2 3 2 1 3 3 1 3 3 2
输出 #1
1 2 3 5 358642921
注意
在第一个测试用例中,$$$a$$$ 只有 $$$1$$$ 不同的排列:
- $$$[1, 1, 1, 1]$$$ 具有 $$$1$$$ 组件。
- 因此组件的预期值为 $$$\frac{1}{1} = 1$$$
在第二个测试用例中,有 $$$4$$$ 方法来排列循环数组 $$$a$$$,但只有 $$$1$$$ 不同的 $$$a$$$ 排列:
- $$$[1, 1, 1, 2]$$$、$$$[1, 1, 2, 1]$$$、$$$[1, 2, 1, 1]$$$ 和 $$$[2, 1, 1, 1]$$$ 是相同的排列,并具有 $$$2$$$ 组件。
- 因此组件的预期值为 $$$\frac{2}{1} = 2$$$
在第三个测试用例中,有 $$$6$$$ 种方法来排列循环数组 $$$a$$$,但 $$$a$$$ 只有 $$$2$$$ 不同的排列:
- $$$[1, 1, 2, 2]$$$、$$$[2, 1, 1, 2]$$$、$$$[2, 2, 1, 1]$$$ 和 $$$[1, 2, 2, 1]$$$ 是相同的排列,并具有 $$$2$$$ 组件。
- $$$[1, 2, 1, 2]$$$ 和 $$$[2, 1, 2, 1]$$$ 是相同的排列,并具有 $$$4$$$ 组件。
- 因此组件的预期值为 $$$\frac{2+4}{2} = \frac{6}{2} = 3$$$
在第四个测试用例中,有 $$$120$$$ 方法来排列循环数组 $$$a$$$,但 $$$a$$$ 的不同排列只有 $$$24$$$:
- $$$a$$$ 的任何排列都有 $$$5$$$ 组件。
- 因此组件的预期值为 $$$\frac{24\cdot 5}{24} = \frac{120}{24} = 5$$$