题目描述

有一棵包含 $N$ 个顶点的树，顶点编号为从 $1$ 到 $N$。每条边将两个顶点相连，其中第 $i$ 条边连接顶点 $u_i$ 和 $v_i$。

最开始，所有顶点上都写着数字 $1$。

你可以进行以下操作任意次（也可以一次都不进行）：

• 从树中选择一个顶点 $v$。将与 $v$ 相邻的所有顶点上的数值做 XOR 运算，得到结果 $X$。然后，将顶点 $v$ 上的数值 $a_v$ 替换为 $(a_v\ \mathrm{XOR}\ X)$。

你需要计算通过这些操作可以得到多少种不同的树形态。由于结果可能非常大，请输出它对 $998244353$ 取模的值。

在这里，两个树形态被认为不同，如果存在至少一个顶点 $v$ 使得这两个形态在该顶点上的数字不同。

输入格式

输入依次包括：

$N$ $u_1$ $v_1$ $u_2$ $v_2$ $\cdots$ $u_{N-1}$ $v_{N-1}$

输出格式

输出表示可以达到的不同树形态数量对 $998244353$ 取模的结果。

样例 1

输入

4
1 2
2 3
3 4

输出

10

样例 2

输入

5
1 2
1 3
1 4
1 5

输出

24

样例 3

输入

6
1 3
2 3
3 4
4 5
4 6

输出

40

样例 4

输入

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

输出

255

说明/提示

• $3 \le N \le 2 \cdot 10^5$
• $1 \le u_i, v_i \le N$
• $u_i \neq v_i$
• 输入表示的图是一棵树。

样例解释 1

假设在顶点 $1, 2, 3, 4$ 上分别写着 $a, b, c, d$。可能的不同形态包括 $1111$、$1110$、$1100$、$1000$、$0111$、$0110$、$0100$、$0011$、$0010$、$0001$。

本翻译由 AI 自动生成