Little H is playing a game.

This is a city construction game, and there are $n$ cities in the game.

To enable communication between cities, Little H has connected them using $n-1$ edges. For any edge $(x, y)$, it is guaranteed that city $x$ and city $y$ can communicate directly. Through these edges, any two cities can communicate either directly or indirectly.

It is not difficult to see that the above approach has some problems. For any two cities, the more intermediate stations they need to pass through, the longer it takes to send information. This leads to some cities having convenient communication, while others do not.

However, increasing the number of edges would make it impossible for Little H to manage the network. To solve this contradiction, Little H came up with a method: every fixed period of time, the network is reconstructed randomly. In this way, the expected communication time between any two cities is equal.

However, reconstructing the network also comes at a cost. Suppose the original network is $T_1$ and the new network is $T_2$. If the two networks share $x$ edges, Little H can ignore these edges during the adjustment.

Naturally, the more edges that can be ignored, the better. Therefore, Little H considers the value of this scheme to be $x \cdot 2^x$.

Now, Little H is about to perform the first network reconstruction. What is the sum of the values of all possible schemes?

Since this answer is quite large, you only need to output the result modulo $998244353$.

Formal Problem Statement

Given a tree $T_1=\{V, E_1\}$ with $|V|=n$, let $S$ be the set of all spanning trees that can be formed by the set of vertices $V$. You need to calculate:

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

It is not difficult to see that $|S|=n^{n-2}$.

Input

The first line contains an integer $n$.

The next $n-1$ lines each contain two integers $x_i, y_i$, describing an edge in $T_1$.

Output

Output a single line representing the sum of the values modulo $998244353$.

Examples

Input 1

4
1 2
2 3
3 4

Output 1

94

Note 1

For spanning trees containing $3$ edges, there is only $1$ such tree. Thus, the contribution is $3 \times 2^3 = 24$.

For spanning trees containing $2$ edges, we analyze by cases. If $(1, 2)$ or $(3, 4)$ is not selected, there are $2$ such trees for each case. If $(2, 3)$ is not selected, there are $3$ such trees. Thus, the contribution is $7 \times 2 \times 2^2 = 56$.

For spanning trees containing $1$ edge, if $(1, 2)$ or $(3, 4)$ is selected, there are $2$ such trees for each case. If $(2, 3)$ is selected, there are $3$ such trees. Thus, the contribution is $7 \times 2 = 14$.

The answer is $24 + 56 + 14 = 94$.

Subtasks

This problem uses bundled testing.

For all data, $1 \le n \le 2\times 10^6$.

The subtasks are shown in the table below:

The special properties in the table are as follows:

• Special Property A: The graph is a chain.
• Special Property B: The graph is a star graph.

Note

The I/O volume for this problem is large; please use fast I/O methods.