Определим ранг неориентированного графа как ранг его матрицы смежности в \(\mathbb{R}^{n \times n}\).
Дано дерево. Каждое из рёбер дерева исчезает с вероятностью \(1/2\) независимо от остальных. Пусть \(E\) — математическое ожидание ранга полученного леса. Найдите остаток от деления \(E \cdot 2^{n-1}\) на \(998244353\) (несложно показать, что \(E \cdot 2^{n-1}\) — целое число).
Выходные данные
Выведите одно число — ответ на задачу.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 2
2 3
|
6
|
|
2
|
4
1 2
1 3
1 4
|
14
|
|
3
|
4
1 2
2 3
3 4
|
18
|