Дед Мороз получил письма от \(n\) разных детей в течение всего этого года. Конечно, каждый ребенок хочет получить от Деда Мороза какие-то подарки: в частности, \(i\)-й малыш попросил подарить ему один из \(k_i\) различных предметов в качестве подарка. Некоторые предметы могли попросить несколько детей.
Дед Мороз очень занят, поэтому он хочет, чтобы Новогодний Робот выбрал подарки для всех детей. К сожалению, алгоритм выбора подарков Роботом содержит ошибку. Чтобы выбрать подарок для какого-то малыша, Робот делает следующее:
- равновероятно выбирает одного ребенка \(x\) среди всех \(n\) детей;
- равновероятно выбирает некоторый предмет \(y\) среди всех \(k_x\) предметов, которые хочет ребенок \(x\);
- равновероятно выбирает ребенка \(z\), который получит подарок, среди всех \(n\) детей (этот выбор не зависит от выбора \(x\) и \(y\)); результирующая тройка \((x, y, z)\) называется выбором Робота.
Если ребенок \(z\) хотел получить предмет \(y\), то выбор корректный. В противном случае, выбор Робота будет некорректным.
Дед Мороз знает об ошибке, но он не может оценить, действительно ли эта ошибка серьезна. Для этого он хочет знать вероятность того, что один выбор, сгенерированный в соответствии с вышеупомянутым алгоритмом, корректен. Вы можете ему помочь?
Выходные данные
Выведите вероятность того, что Робот сделает корректный выбор следующим образом:
Пусть эта вероятность представлена в виде неприводимой дроби \(\frac{x}{y}\). Вам необходимо вывести \(x \cdot y^{-1} \mod 998244353\), где \(y^{-1}\) является обратным элементом к \(y\) по модулю \(998244353\) (такое целое число, что \(y \cdot y^{-1}\) имеет остаток \(1\) по модулю \(998244353\)).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
2 2 1
1 1
|
124780545
|
|
2
|
5
2 1 2
2 3 1
3 2 4 3
2 1 4
3 4 3 2
|
798595483
|