题目描述

对于一个无向树 $t$，我们定义一个有理数 $f(t)$ 如下。

• 让 $n$ 为 $t$ 中的顶点数。
• 如果 $n=1$：令 $f(t)=1$。
• 如果 $n \geq 2$：
  • 对于 $t$ 中的一条边 $e$，我们用 $t_x(e)$ 和 $t_y(e)$ 表示从 $t$ 中删除 $e$ 后得到的两棵子树（任意顺序）。
  • 令 $f(t)=(\\sum_{e \\in t} f(t_x(e)) \\times f(t_y(e)))/n$。

给定一棵有 $N$ 个顶点编号为 $1$ 到 $N$ 的树 $T$。第 $i$ 条边连接顶点 $A_i$ 和顶点 $B_i$。

计算值 $f(T)$ $\\text{mod }{998244353}$。

什么是有理数 $\\text{mod }{998244353}$？

在本问题的约束下，当待求的有理数表示为 $\\frac{P}{Q}$ 时，可以证明 $Q \\neq 0 \\pmod{998244353}$。因此，存在唯一的整数 $R$ 使得 $R \\times Q \\equiv P \\pmod{998244353}$，且 $0 \\leq R < 998244353$。找到这个 $R$。

约束条件

• $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}$

输出

打印答案。

样例输入 1

2
1 2

样例输出 1

499122177

我们有 $f(T)=1/2$。

样例输入 2

3
1 2
2 3

样例输出 2

332748118

我们有 $f(T)=1/3$。

样例输入 3

4
1 2
2 3
3 4

样例输出 3

103983787

样例输入 4

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

样例输出 4

462781191