Description

The little hamster and his buddy sugar live in an underground cave system. Each node is an integer between $1 \sim n$. The cave system is a tree (each edge has length $1$). On this day the hamster plans to go from his bedroom $a$ (arbitrary) to his buddy’s bedroom $b$ (also arbitrary) (note that $a$ may be equal to $b$). However, after studying OI too hard, he has gone silly and does not know how to take the shortest path, so he just walks randomly. When he is at a node, he moves with equal probability to its parent or any of its children (for example, if this node has one parent and two children, then the probability of moving to each of these $3$ neighbors is $\dfrac{1}{3}$). Once he reaches $b$, he stops.

Now the little hamster wants to know the expected number of steps when he reaches the destination. This expectation is a rational number. To avoid precision errors, we ask you to output this rational number modulo $998,244,353$.

Formally, it can be shown that the answer can be written as an irreducible fraction $\dfrac{y}{x}$, where $x \not\equiv 0 \pmod{998,244,353}$. It can be shown that there exists a unique integer $z$ ($0 \le z \lt 998,244,353$) such that $x z \equiv y \pmod{998,244,353}$; you only need to output the value of $z$.

The little hamster is so weak and always gets beaten by JOHNKRAM. Please help him!

Input Format

The first line contains a positive integer $n$, the number of nodes in the tree.

The next $n-1$ lines each contain two positive integers $u$ and $v$, indicating that there is an edge between nodes $u$ and $v$.

Output Format

Output a single integer, the answer modulo $998,244,353$.

3
1 2
1 3

110916041

Hint

Sample explanation: the true expected value is $\dfrac {16}{9}$.

If $a$ is a leaf and $b$ is the root, then the expectation is $\mathbb{E}_1=1$. There are $2$ cases.

If $a$ is the root and $b$ is a leaf, then $\displaystyle \mathbb{E}_2=\frac{1}{2}+\frac{3}{4}+\frac{5}{8}+\cdots=3$. There are $2$ cases.

If $a,b$ are different leaves, then $\mathbb{E}_3=\mathbb{E}_2+1=4$. There are $2$ cases.

If $a=b$, then $\mathbb{E}_4=0$. There are $3$ cases.

So the answer is $\displaystyle \frac{2\times 1+2\times 3+2\times 4+3\times 0}{2+2+2+3}=\frac{16}{9}$.

Since $110,916,041\times 9=998,244,369\equiv 16\pmod {998,244,353}$, output $110,916,041$.

For $30\%$ of the testdata, $n\le 5$.

For $50\%$ of the testdata, $n\le 5,000$.

For all testdata, $n\le 100,000$.

$\text{Statement fixed by @Starrykiller.}$

Translated by ChatGPT 5