配点 : $2000$ 点

問題文

$N$ 頂点の木が与えられます。 木の頂点には $1$ から $N$ までの番号が付けられており、$i$ 番目の辺は頂点 $u_i, v_i$ を結びます。

はじめ、木の各頂点には $1$ という数が書かれています。

$1$ 回の操作で、あなたは以下を行えます。

• 木から頂点 $v$ を選ぶ。$v$ に隣接する頂点全てに書き込まれた値の XOR が $X$ であるとする。$v$ に書かれた値が $a_v$ であるとして、この値を $(a_v\ \mathrm{XOR}\ X)$ に置き換える。

この操作を任意の有限回（$0$ 回も含む）行えるとして、得られる木の形態は何通りあるでしょうか。この数は大きい可能性があるため、これを $998244353$ で割った余りを出力してください。

ここで、木の $2$ つの形態は、書かれた数が異なるような頂点 $v$ が存在するときに異なるとみなされます。

制約

• $3 \le N \le 2\cdot 10^5$
• $1\le u_i, v_i \le N$
• $u_i \neq v_i$
• 入力が表すグラフは木である。

入力

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

$N$

$u_1$ $v_1$

$u_2$ $v_2$

$\vdots$

$u_{N-1}$ $v_{N-1}$

出力

初期状態から得られる木の形態の個数を $998244353$ で割った余りを出力せよ。

4
1 2
2 3
3 4

10

頂点 $1,2,3,4$ に $a,b,c,d$ が書かれている形態を $abcd$ と表すと、到達可能な形態は $1111$, $1110$, $1100$, $1000$, $0111$, $0110$, $0100$, $0011$, $0010$, $0001$ です。

5
1 2
1 3
1 4
1 5

24

6
1 3
2 3
3 4
4 5
4 6

40

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

255