配点 : $2000$ 点

問題文

無向木 $t$ に対して，有理数 $f(t)$ を次のように定義します．

• $t$ の頂点数を $n$ とする．
• $n=1$ のとき：$f(t)=1$ とする．
• $n \geq 2$ のとき：- $t$ の辺 $e$ について，$t$ から $e$ を削除することで得られる $2$ つの木を $t_x(e),t_y(e)$ （順不同）で表す．
  • $f(t)=(\sum_{e \in t} f(t_x(e)) \times f(t_y(e)))/n$ とする．
• $t$ の辺 $e$ について，$t$ から $e$ を削除することで得られる $2$ つの木を $t_x(e),t_y(e)$ （順不同）で表す．
• $f(t)=(\sum_{e \in t} f(t_x(e)) \times f(t_y(e)))/n$ とする．

$1$ から $N$ までの番号のついた $N$ 頂点からなる木 $T$ が与えられます． $i$ 番目の辺は頂点 $A_i$ と頂点 $B_i$ を結ぶ辺です．

$f(T)$ の値を $\text{mod }{998244353}$ で求めてください．

制約

• $2 \leq N \leq 5000$
• $1 \leq A_i,B_i \leq N$
• 入力されるグラフは木である

入力

入力は以下の形式で標準入力から与えられる．

$N$

$A_1$ $B_1$

$A_2$ $B_2$

$\vdots$

$A_{N-1}$ $B_{N-1}$

出力

答えを出力せよ．

2
1 2

499122177

$f(T)=1/2$ です．

3
1 2
2 3

332748118

$f(T)=1/3$ です．

4
1 2
2 3
3 4

103983787

10
4 5
1 9
6 1
8 4
5 9
4 7
3 10
5 2
4 3

462781191