問題文

$N$ 頂点の木 $T$ があります。各頂点には $1$ から $N$ の番号が付けられており、頂点 $i$ には整数 $A_i$ が書かれています。

また、 $T$ の $i$ 本目の辺は頂点 $u_i$ と $v_i$ を結んでいます。

$T$ の辺をいくつか選んで削除すると、 $T$ は削除した辺の本数を $k$ として $k+1$ 個の連結成分 $T'_1,T'_2,\ldots,T'_{k+1}$ に分かれます。

連結成分 $T'$ のスコアを、$T'$ に含まれる頂点に書かれている整数の最大値を $M$ 、 $T'$ に含まれる頂点の個数を $S$ として、$M×S$ と定めます。

また、辺の削除方法のスコアを、辺の削除によって生じた連結成分たちのスコアの総和と定めます。

辺の削除方法は全部で $2^{N-1}$ 通りありますが、その全てに対する辺の削除方法のスコアの総和を $998244353$ で割った余りを求めてください。

入力

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

• $2\le N\le 5000$
• $1\le A_i\le 1000$
• $1\le u_i,v_i\le N$
• 与えられるグラフは木
• 入力はすべて整数

出力

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

サンプル

3
2 4 6
1 2
1 3

60

7
4 2 5 9 10 3 12
1 3
2 3
3 5
3 4
3 7
5 6

4008