Дан неориентированный граф с \(n\) вершинами и \(m\) рёбрами. Каждое ребро соединяет две вершины \((u, v)\) и каждый день появляется с вероятностью \(\frac{p}{q}\).
Изначально в вершине \(1\) есть сообщение. В конце дня вершина имеет сообщение тогда и только тогда, когда сама она или хотя бы одна из смежных с ней вершин имела сообщение в прошлый день. Обратите внимание, что каждый день ребро выбирает своё появление независимо.
Вычислите математическое ожидание количества дней, прежде чем все вершины получат сообщение, по модулю \(998\,244\,353\).
Выходные данные
Выведите одно целое число в единственной строке вывода — математическое ожидание количества дней, по модулю \(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}\).
Примечание
В первом тесте ответ равен математическому ожиданию количества дней, прежде чем появится единственное ребро в графе, и оно равно \(\frac{1}{0.1}=10\).
Во втором тесте ответ равен \(\frac{20}{9}\), прежде чем он будет взят по модулю \(998\,244\,353\).
В третьем тесте единственная вершина уже имеет сообщение, поэтому ответ равен \(0\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 1
1 2 1 10
|
10
|
|
2
|
3 3
1 2 1 2
1 3 1 2
2 3 1 2
|
887328316
|
|
3
|
1 0
|
0
|
|
4
|
5 8
1 2 1 11
1 3 2 11
1 4 3 11
1 5 4 11
2 4 5 11
2 5 6 11
3 4 7 11
4 5 8 11
|
469993557
|
|
5
|
21 22
1 2 3 4
2 3 4 5
3 4 5 6
5 6 7 8
6 7 8 9
7 8 9 10
8 9 2 3
9 10 3 4
10 11 4 5
11 12 5 6
12 13 6 7
13 14 7 8
14 15 8 9
15 16 9 10
16 17 2 3
17 18 3 4
18 19 4 5
19 20 5 6
20 21 6 7
1 10 100 1001
15 4 147 220
4 11 1 998244352
|
299529765
|