問題文

長さ $N$ の非負整数列 $A=(A_1,A_2,\dots,A_N)$ と $N$ 頂点からなる木が与えられます。頂点には $1$ から $N$ の番号がついており、$i$ 番目の辺は頂点 $U_i,V_i$ を結んでいます。

相異なる $2$ 頂点 $i,j$ 間のコスト $f(i,j)$ を次のように定義します。

• 頂点 $i,j$ を結ぶ単純パス上の頂点を順に $p_1(=i),p_2,\dots,p_k(=j)$ とする。ここで $k$ はパスに含まれる頂点数である。 このとき、 $f(i,j)=A_{p_1}\times A_{p_2} \times \dots \times A_{p_k}$ で定める。

$\displaystyle\sum_{i=1}^{N-1}\sum_{j=i+1}^{N} f(i,j)$ を $998244353$ で割ったあまりを求めてください。

制約

• $2\leq N\leq 2\times 10^5$
• $0\leq A_i< 998244353$
• $1\leq U_i,V_i\leq N$
• 入力はすべて整数である。
• 与えられるグラフは木である。

入力

$N$
$A_1$ $A_2$ $\dots$ $A_N$
$U_1$ $V_1$
$U_2$ $V_2$
$\vdots$
$U_{N-1}$ $V_{N-1}$

出力

$\displaystyle\sum_{i=1}^{N-1}\sum_{j=i+1}^{N} f(i,j)$ を $998244353$ で割ったあまりを出力してください。

サンプル

4
1 2 3 4
1 2
2 3
2 4

54

2
0 0
1 2

0

10
810284561 609063208 909877398 113848143 744347504 567699714 418423327 541843429 325332295 953873148
10 6
5 10
2 5
4 2
9 6
3 10
8 3
7 10
1 6

318883473