問題文

$N$ 頂点の木 $T$ があり、各頂点には $1$ から $N$ までの番号が振られています。
$i$ 番目の辺は頂点 $u_i$ と頂点 $v_i$ を結んでいます。頂点 $i$ には非負整数 $A_i$ が書かれています。

木 $T$ から $0$ 本以上の辺を削除して得られるグラフ $G$ は $2^{N-1}$ 通りありますが、
それぞれのグラフ $G$ について $f(G)$ の値を求めて、その総和を $998244353$ で割った余りを求めてください。

ここで、$f(G)$ とは、グラフ $G$ の連結成分ごとに $A_i$ の $\mathrm{XOR}$ を取り、それらの値の $\mathrm{AND}$ を取った値です。
より厳密には以下の通りです。

• $f(G) = g(C_1) \ \mathrm{AND} \ \cdots \ \mathrm{AND} \ g(C_{m_G})$
• $g(C_j) = A_{k_{j,1}} \ \mathrm{XOR} \ \cdots \ \mathrm{XOR} \ A_{k_{j,n_j}} \ (1 \leq j \leq m_G)$
• グラフ $G$ の連結成分は $m_G$ 個あり、$C_1, \dots , C_{m_G}$ で表される
• 連結成分 $C_j$ の頂点は $n_j$ 個あり、$k_{j,1}, \dots , k_{j,n_j}$で表される

なお、$\mathrm{AND}$ はビット単位 $\mathrm{AND}$ 演算、$\mathrm{XOR}$ はビット単位 $\mathrm{XOR}$ 演算を表します。

入力

$N$
$u_1 \ v_1$
$u_2 \ v_2$
$\vdots$
$u_{N-1} \ v_{N-1}$
$A_1 \ A_2 \ \dots \ A_N$

• $2 \leq N \leq 10^5$
• $0 \leq A_i < 2^{30}$
• $1 \leq u_i, v_i \leq N$
• 与えられるグラフは木
• 入力はすべて整数

出力

答えを出力してください。

サンプル

3
1 2
1 3
1 2 3

5

12
1 2
1 7
2 3
2 4
2 6
3 11
4 5
4 8
5 10
8 9
8 12
353757523 442052636 38474683 454295822 886828797 329385635 709686492 100655361 541398767 782865336 996474425 506498311

159370513