Problem Statement

There is a tree $T$ with $N$ vertices. The vertices are numbered from $1$ to $N$, and the integer $A_i$ is written on vertex $i$.

The $i$-th edge of $T$ connects vertices $u_i$ and $v_i$.

If we choose some edges of $T$ and delete them, $T$ splits into $k+1$ connected components $T'_1,T'_2,\ldots,T'_{k+1}$, where $k$ is the number of deleted edges.

The score of a connected component $T'$ is defined as $M×S$, where $M$ is the maximum of the integers written on the vertices contained in $T'$, and $S$ is the number of vertices contained in $T'$.

The score of a way of deleting edges is defined as the sum of the scores of the connected components resulting from the deletion.

There are $2^{N-1}$ ways of deleting edges in total. Find the sum of the scores over all of these ways, modulo $998244353$.

Input

$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 10^5$
• $1\le A_i\le 998244352$
• $1\le u_i,v_i\le N$
• The given graph is a tree.
• All input values are integers.

Output

Output the answer.

Sample

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