Задача . F. Сильносвязный турнир

В городе Нормгород проходит шахматный турнир. n игроков были приглашены для участия в нём. Турнир проходит по следующим правилам:

1. Каждый игрок играет с каждым другим одну партию, ничьих не бывает;
2. После этого организаторы строят полный ориентированный граф, вершинами которого являются игроки. Для каждой пары игроков в графе есть одно ребро, начало которое идет от победителя игры между ними к проигравшему;
3. После этого граф конденсируется. Так как исходный граф полный, то его конденсация — ацикличный полный ориентированный граф, в котором есть единственный гамильтонов путь из компонент сильной связности исходного графа A₁ → A₂ → ... → A_k;
4. Игроки из первой компоненты сильной связности A₁ занимают первые мест, игроки из компоненты A₂ занимают следующие мест, и так далее;
5. Для того, чтобы определить, кто какое место занял внутри каждой компоненты сильной связности, все шаги с 1 по 5 повторяются рекурсивно для каждой компоненты, то есть, для всех i = 1, 2, ..., k все игроки из компоненты A_i снова играют друг с другом партию, и так далее.
6. Если компонента сильной связности состоит из одного человека, то ему больше не с кем играть, его место уже однозначно определено, и процесс останавливается.

Игроки пронумерованы числами от 1 до n. Нумерация была выполнена по результатам прошлого турнира. Известно, что игрок с номером i побеждает игрока с номером j с вероятностью p при i < j.

Вам поручено помочь с организацией турнира. Найдите математическое ожидание суммарного количества партий, сыгранных всеми игроками.

Можно показать, что ответ может быть выражен как , где P и Q — взаимно простые целые числа, а . Выведите значение P·Q^- 1 по модулю 998244353.

Если вы не знакомы с понятиями теории графов, используемыми выше, вы можете ознакомиться с ними по ссылке.