Дан кольцевой массив \(a\) размера \(n\), где \(a_i\) равно значению \(a\) в \(i\)-й позиции, значения могут повторяться. Пусть перестановка \(a\) равна другой перестановке \(a\) тогда и только тогда, когда их значения равны в каждой позиции \(i\) или можно сделать из одной перестановки другую циклическим сдвигом. Положим в качестве количества компонент циклического массива \(b\) количество компонент связности в графе, в котором вершины — это позиции \(b\), и между двумя соседними позициями \(b\) существует ребро, если значения в этих позициях равны (заметьте, что в кольцевом массиве первая и последняя позиции считаются соседними).
Найдите математическое ожидание количества компонент перестановки \(a\), если мы равновероятно выбираем ее из множества всех различных перестановок \(a\).
Выходные данные
Для каждого набора входных данных напечатайте одно целое число — математическое ожидание количества компонент перестановки \(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}\).
Примечание
В первом наборе существует только \(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\)
Примеры
| № | Входные данные | Выходные данные |
|
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
2
3
5
358642921
|