harurun君の家には一本の立派な木が生えています。 harurun君はこの木を切ったり接着剤でくっつけたりして一本の長い棒を作ろうと考えました。
頂点に $1$ から $N$ の番号が、辺に $1$ から $N-1$ の番号がついた $N$ 頂点の木グラフが与えられます。 辺 $i$ は頂点 $u_i$ と $v_i$ を結んでいます。
$A$ を空の配列とし、以下の操作を $0$ 回以上好きな回数行うことを考えます。
上記の操作を繰り返した結果、グラフがパスグラフになったときの、ありうる配列 $A$ の種類数を求めてください。 答えは大きくなる可能性があるため、 $998244353$ で割ったあまりを出力してください。
ただし、パスグラフとは、各頂点の次数が高々 $2$ であるような木グラフを指します。
$N$
$u_1\ v_1$
$u_2\ v_2$
$\vdots$
$u_{N-1}\ v_{N-1}$
答えを $998244353$ で割ったあまりを $1$ 行に出力してください。
4 1 3 1 4 2 3
9
ありうる配列 $A$ は以下の通りです。
与えられるグラフがパスグラフである場合は、 $A$ が空の配列でも条件を満たすことに注意してください。
20 1 13 2 13 3 18 4 13 4 14 4 15 5 7 6 19 7 10 8 15 9 15 10 13 10 17 10 19 11 12 12 13 12 16 13 18 15 20
16984504
$998244353$ で割ったあまりを出力することに注意してください。