Mały H gra w grę.

Jest to gra polegająca na budowaniu miast, w której istnieje $n$ miast.

Aby umożliwić komunikację między miastami, Mały H połączył je za pomocą $n-1$ krawędzi. Dla każdej krawędzi $(x,y)$ zagwarantowane jest, że miasto $x$ i miasto $y$ mogą się bezpośrednio komunikować. Dzięki tym krawędziom dowolne dwa miasta mogą komunikować się bezpośrednio lub pośrednio.

Łatwo zauważyć, że powyższe podejście ma pewne wady. Im więcej punktów przesiadkowych muszą pokonać informacje między dwoma miastami, tym dłuższy jest czas potrzebny na ich przesłanie. Prowadzi to do sytuacji, w której niektóre miasta mają dogodną komunikację, a inne nie.

Jednak zwiększenie liczby krawędzi sprawiłoby, że sieć stałaby się dla Małego H zbyt trudna w zarządzaniu. Aby rozwiązać ten konflikt, Mały H wymyślił sposób: po upływie określonego czasu sieć jest przebudowywana w sposób losowy. Dzięki temu oczekiwany czas komunikacji między dowolnymi dwoma miastami jest taki sam.

Niemniej jednak przebudowa sieci również wiąże się z kosztami. Załóżmy, że pierwotna sieć to $T_1$, a nowa sieć to $T_2$. Jeśli oba sieci mają $x$ wspólnych krawędzi, Mały H może pominąć te krawędzie podczas dostosowywania.

Naturalnie, im więcej krawędzi można pominąć, tym lepiej, dlatego Mały H uważa, że wartość takiego rozwiązania wynosi $x\cdot 2^x$.

Teraz Mały H przeprowadzi pierwszą przebudowę sieci. Jaka jest suma wartości wszystkich możliwych rozwiązań?

Oczywiście wynik ten może być bardzo duży, dlatego należy podać go modulo $998244353$.

Formalizacja zadania

Dane jest drzewo $T_1=\{V,E_1\}$, gdzie $|V|=n$. Niech $S$ będzie zbiorem wszystkich drzew rozpinających, które można utworzyć na zbiorze wierzchołków $V$. Należy obliczyć:

$$\left(\sum_{T_2\in S} |E_1\cap E_2|\cdot 2^{|E_1\cap E_2 |}\right) \bmod 998244353 $$

Łatwo zauważyć, że $|S|=n^{n-2}$.

Wejście

Pierwsza linia zawiera liczbę całkowitą $n$.

Następnie $n-1$ linii, z których każda zawiera dwie liczby całkowite $x_i, y_i$, opisujące krawędź w $T_1$.

Wyjście

Wypisz jedną linię zawierającą sumę wartości modulo $998244353$.

Przykład

Wejście 1

4
1 2
2 3
3 4

Wyjście 1

94

Uwagi

Dla drzew rozpinających zawierających $3$ krawędzie istnieje tylko $1$ możliwość. Wkład wynosi $3\times 2^3=24$.

Dla drzew rozpinających zawierających $2$ krawędzie rozważamy przypadki. Jeśli nie wybrano $(1,2)$ lub $(3,4)$, istnieją po $2$ możliwości. Jeśli nie wybrano $(2,3)$, istnieją $3$ możliwości. Wkład wynosi $7\times 2 \times 2^2=56$.

Dla drzew rozpinających zawierających $1$ krawędź, jeśli wybrano $(1,2)$ lub $(3,4)$, istnieją po $2$ możliwości. Jeśli wybrano $(2,3)$, istnieją $3$ możliwości. Wkład wynosi $7\times 2=14$.

Odpowiedź wynosi $24+56+14=94$.

Wskazówki

Zadanie charakteryzuje się dużą ilością danych wejściowych, prosimy o stosowanie szybkich metod wczytywania.

Podzadania

Zadanie oceniane jest w systemie pakietowym.

Dla wszystkich danych wejściowych spełniony jest warunek $1 \le n \le 2\times 10^6$.

Podzadania przedstawiono w poniższej tabeli:

Własności specjalne w tabeli:

• Własność A: Graf jest ścieżką.
• Własność B: Graf jest gwiazdą.