У вас есть мешок с \(n\) карточками. На каждой карточке написано какое-то число; на \(i\)-й карточке написано число \(a_i\).
Вы играете в следующую игру. Во время каждого хода вы берете и удаляете случайную карточку из мешка (все карточки, оставшиеся в мешке, выбираются равновероятно). Больше ничего в первый ход не происходит, но во время каждого следующего хода после удаления карточки из мешка (обозначим число, написанное на ней, как \(x\)) вы сравниваете ее с карточкой, которая была удалена на предыдущий ход (обозначим число, написанное на ней, как \(y\)). Есть три возможных варианта:
- если \(x < y\), вы проиграли, игра заканчивается;
- если \(x = y\), вы выиграли, игра заканчивается;
- если \(x > y\), игра продолжается.
Если в мешке не осталось карточек — вы проиграли. Карточки не возвращаются в мешок после того, как вы их удалили.
Вам нужно посчитать вероятность выиграть в этой игре. Можно показать, что ответ может быть представлен в виде несократимой дроби \(\frac{P}{Q}\), где \(P\) и \(Q\) — положительные целые числа, и \(Q \neq 0\), \(P \le Q\). Вам нужно вывести \(P \cdot Q^{−1} ~(mod ~~ 998244353)\).
Примечание
В первом тестовом примере вероятность выиграть равна \(\frac{1}{10}\).
Во втором тестовом примере вероятность выиграть равна \(1\).
В третьем тестовом примере вероятность выиграть равна \(0\).
В четвертом тестовом примере вероятность выиграть равна \(\frac{1}{4}\).