Problem Statement

There is a tree with $N$ vertices numbered from $1$ to $N$, where the $i$-th edge connects vertices $A_i$ and $B_i$.

We will now randomly write real numbers between $-(N-1)$ and $1$ (inclusive) on each vertex of this tree. The random number distributions are all independent uniform distributions.

Then, the score of the tree is defined as follows:

• For each vertex $i$, define $x_i$ as follows:
• The maximum value of the sum of values written on vertices of connected subgraphs that contain vertex $i$
• If there exists $i$ that does not satisfy $0 \leq x_i \leq 1$, the tree's score is $0$.
• Otherwise, the tree's score is $\prod_{1 \leq i \leq N} x_i$.

Find the expected value $\text{mod }{998244353}$ of the tree's score.

Definition of expected value $\text{mod }{998244353}$ It can be proved that the sought expected value is always a rational number. Also, under the constraints of this problem, it can be proved that when the value is expressed as an irreducible fraction $\frac{P}{Q}$, we have $Q \neq 0 \pmod{998244353}$. Therefore, an integer $R$ satisfying $R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353$ is uniquely determined. Answer this $R$.

Constraints

• $1 \leq N \leq 5000$
• $1 \leq A_i, B_i \leq N$
• The input graph is a tree.

Input

The input is given from Standard Input in the following format:

N
A_1 B_1
A_2 B_2
\vdots
A_{N-1} B_{N-1}

Output

Output the answer.