Dla zbioru $S$ ścieżek w drzewie, definiujemy $f(S)$ jako rozmiar największego podzbioru $T \subseteq S$, takiego że ścieżki w $T$ są parami rozłączne wierzchołkowo. Przyjmujemy, że para $(x, y)$ reprezentuje ścieżkę.
Dla zbioru wszystkich ścieżek $P = \{ (x, y) \mid 1 \le x, y \le n \}$, oblicz:
$$\sum_{S \subseteq P} f(S)$$
Oznacza to, że należy obliczyć sumę wartości $f$ dla wszystkich $2^{n^2}$ możliwych zbiorów. Wynik należy podać modulo 998244353.
Wejście
Pierwsza linia zawiera liczbę całkowitą $n$, oznaczającą liczbę wierzchołków w drzewie.
Kolejne $n-1$ linii zawiera po dwie liczby całkowite $u, v$, oznaczające krawędź w drzewie.
Wyjście
Wypisz jedną liczbę całkowitą, oznaczającą wynik modulo 998244353.
Przykład 1
Wejście 1
2 1 2
Wyjście 1
19
Uwagi
Zbiór o wartości $f$ równej 0 to $\emptyset$. Zbiory o wartości $f$ równej 2 muszą zawierać $(1, 1)$ oraz $(2, 2)$, podczas gdy $(1, 2)$ i $(2, 1)$ można wybrać dowolnie, co daje 4 możliwości. Pozostałe 11 zbiorów ma wartość $f$ równą 1, zatem odpowiedź wynosi $0 \times 1 + 1 \times 11 + 2 \times 4 = 19$.
Przykład 2
Wejście 2
5 1 2 2 3 3 4 4 5
Wyjście 2
103767551
Podzadania
Dla 100% danych wejściowych zachodzi $1 \le n \le 5000$.
| Test | $n$ | Ograniczenia specjalne |
|---|---|---|
| 1 | $= 2$ | |
| 2 | $= 3$ | |
| 3 | $= 4$ | |
| 4 | $= 5$ | |
| 5, 6 | $= 200$ | |
| 7 | $= 5000$ | A |
| 8 | $= 5000$ | B |
| 9, 10 | $= 5000$ |
Ograniczenia specjalne: A oznacza zbiór krawędzi $\{(1, 2), (2, 3), \dots, (n-1, n)\}$. B oznacza zbiór krawędzi $\{(1, 2), (1, 3), \dots, (1, n)\}$.