E. Ожидаемые компоненты
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан кольцевой массив $$$a$$$ размера $$$n$$$, где $$$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$$$.

Формально, пусть $$$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}$$$.

Пример
Входные данные
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
2
3
5
358642921
Примечание

В первом наборе существует только $$$1$$$ перестановка $$$a$$$:

  • $$$[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$$$, но существует только $$$2$$$ различные перестановки $$$a$$$:

  • $$$[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$$$, но существует только $$$24$$$ различные перестановки $$$a$$$:

  • Любая перестановка $$$a$$$ содержит $$$5$$$ компонент.
  • Поэтому математическое ожидание количества компонент равно $$$\frac{24\cdot 5}{24} = \frac{120}{24} = 5$$$