题目描述

小 H 在玩一款城市建设游戏。

这是一款对城市进行建设的游戏，游戏里有 $n$ 个城市。

为了使城市之间能够通信，小 H 用 $n-1$ 条边连接了城市。对于一条边 $(x,y)$，它保证了城市 $x$ 和城市 $y$ 能直接通信。通过这些边，任意两个城市能够直接或间接通信。

不难发现，上述做法存在一些问题。对于两座城市，如果它们之间需要经过的中转站越多，那么每次发送信息所需要的时间就越长。这就导致一些城市通信便利，一些城市通信不便利。

然而，增加边的数量会导致小 H 无法管理而出现问题。为了解决这个矛盾，小 H 想出了一个办法，每经过一段固定的时间，就重新随机的构建一次网络。这样一来，任意两个城市通信时间的期望值都是相等的。

然而，重构网络也是需要代价的。假设原网络为 $T_1$，新网络为 $T_2$，假设两个网络有 $x$ 条边是一样的，那么小 H 在调整时就可以忽略这些边。

自然，能忽略的边越多越好，因此小 H 认为这种方案的价值为 $x \cdot 2^x$。

现在，小 H 将进行第一次网络重构，请问，所有方案的价值之和为多少？

当然，这个答案比较大，所以你只需要求其对 $998244353$ 取模的值。

形式化题目

给定树 $T_1=\{V,E_1\}$（$|V|=n$），假设点集 $V$ 能构成的生成树集合为 $S$，你需要求：

$$\left( \sum_{T_2 \in S} |E_1 \cap E_2| \cdot 2^{|E_1 \cap E_2|} \right) \bmod 998244353 $$

不难发现，$|S|=n^{n-2}$（Cayley 公式）。

输入格式

第一行一个整数 $n$。

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

输出格式

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

样例

• 输入：

  4
  1 2
  2 3
  3 4
  

• 输出：

  94
  

• 解释：
  1. 含 $3$ 条共边的生成树：仅 $1$ 种，贡献为 $3 \times 2^3 = 24$。
  2. 含 $2$ 条共边的生成树：共 $7$ 种，贡献为 $7 \times 2 \times 2^2 = 56$。
     • 未选 $(1,2)$ 或 $(3,4)$ 时，各有 $2$ 种；未选 $(2,3)$ 时，有 $3$ 种。
  3. 含 $1$ 条共边的生成树：共 $7$ 种，贡献为 $7 \times 1 \times 2^1 = 14$。
     • 选 $(1,2)$ 或 $(3,4)$ 时，各有 $2$ 种；选 $(2,3)$ 时，有 $3$ 种。
  4. 总价值：$24 + 56 + 14 = 94$。

数据范围与提示

本题采用捆绑测试，所有数据满足 $1 \le n \le 2 \times 10^6$。

子任务编号	$n$ 范围	特殊性质	分值
1	$\le 80$	无	5
2	$\le 300$
3	$\le 3000$	特殊性质 A
4		特殊性质 B
5		无	10
6	$\le 10^5$	特殊性质 A
7		特殊性质 B
8	$\le 2 \times 10^6$	特殊性质 A
9		特殊性质 B
10		无	30

其中，特殊性质定义如下：

• 特殊性质 A：树是一条链（所有节点依次连接成线性结构）。
• 特殊性质 B：树是一张菊花图（存在一个中心节点，所有其他节点仅与中心节点相连）。

提示：本题 IO 量较大，建议使用较快的读入方法。