题目描述

给定一棵 $n$ 个点的无根树 $T$。对于在同样点集上的一棵 $n$ 个点的无根树 $T'$，不妨设有 $x$ 条边同时出现在 $T$ 与 $T'$ 中，则定义 $T'$ 的权值为 $x\times 2^x$。

现在请你对于完全图的所有 $n^{n-2}$ 棵生成树 $T'$ 求出其权值之和，对 $998244353$ 取模。

输入格式

第一行一个整数 $n$ 。

接下来 $n-1$ 行，每行两个整数 $x_i,y_i$ ，描述 $T$ 上的一条边。

输出格式

输出一行，表示价值之和对 $998244353$ 取模的结果。

样例输入 #1

4
1 2
2 3
3 4

样例输出 #1

94

样例解释 #1

$x=3$ 的生成树有 $1$ 种，$x=2$ 的生成树有 $7$ 种，$x=1$ 的生成树有 $7$ 种，$x=0$ 的生成树有 $1$ 种。

数据范围/提示

本题共 $25$ 个测试点，每个测试点等分。

• 特殊性质 A：图是一条链。
• 特殊性质 B：图是一张菊花图。

请注意程序的输入输出效率，建议使用更快的 IO 实现方式。