問題文

$N$ 頂点 $N-1$ 辺無向グラフが与えられます。与えられるグラフに多重辺、自己ループはありませんが、連結であるとは限りません。

$i$ 本目の辺は、長さ $l_i$ の辺で、始めは $a_i$ と $b_i$ をつないでいます。

グラフがスターグラフ、すなわち完全二部グラフ $K_{1,N-1}$ になるまで、以下の操作を繰り返します。

• 辺をランダムに $1$ 本選びます。それぞれの辺が選ばれる確率は辺の長さに比例します。
• 選んだ辺を消します。
• 間に辺がないような頂点の組は $\frac{N(N-1)}{2}-(N-2)$ 個ありますが、等確率で $1$ 個を選び間を辺でつなぎます。追加する辺の長さは消した辺の長さとします。

操作回数の期待値 $\bmod 998244353$ を求めてください。制約上、解は $\bmod 998244353$ 上で表現可能な有理数であることが確認されています。

制約

• 入力は全て整数である。
• $2 \le N \le 250$
• $1 \le a_i,b_i \le N$
• 与えられるグラフに多重辺、自己ループは存在しない。
• $1 \le l_i \le 2$

入力

$N$
$a_1\ b_1\ l_1$
$a_2\ b_2\ l_2$
$\vdots$
$a_{N-1}\ b_{N-1}\ l_{N-1}$

出力

答えを $1$ 行に出力してください。

サンプル

サンプル1

入力

4
1 2 1
2 3 1
1 3 2

出力

5

例えば、以下の左から真ん中、そして右のように操作が実行される確率は $\displaystyle \frac{2}{4} \times \frac{1}{4} \times \frac{1}{4} \times \frac{1}{4} = \frac{1}{128}$ であり操作回数は $2$ 回です。

また、解は $5$ であることが証明可能です。

3
1 2 1
1 3 2

0

7
1 2 2
2 4 1
3 5 1
4 7 2
1 7 2
3 6 2

602774886