Background

  SWW is a master of Probability. One day, she thought of a problem in her dream and she wants to challenge you.

  She gives you a tree $T$ with $n$ nodes, labeled from $1$ to $n$. Each node of the tree has a positive integer weight $a_i$ . For any connected subgraph of $T$, denoted as $S$, you could collect the weights of all nodes in $S$ and calculate the variance of these weights.

  Now, SWW wants you to calculate the sum of variances of all connected subgraphs of T. Since the answer may be very large, you should print your result modulo $998244353$.

  Recall that for a given set of numbers $x_1, x_2, · · · , x_n$, the mean µx and variance $σ\frac{2}{x}$ is defined as

$$µ_x = \frac{x_1 + x_2 + · · · + x_n}{n}$$ $$σ^2_x=\frac{(x_1 − µ_x)^2 + (x_2 − µ_x)^2 + · · · + (x_n − µ_x)^2}{n} $$

Input

The first line contains an integer $n (1 ≤ n ≤ 300)$, representing the number of tree nodes.

The second line contains $n$ integers $a_1, a_2, · · · , a_n (1 ≤ a_i ≤ 998244352)$, representing the weights of each node.

Each line of the next $n − 1$ lines contains two integers $u, v (1 ≤ u, v ≤ n)$, representing an edge $(u, v)$in the tree. It is guaranteed that the given graph is a tree.

Output

Output a single integer, representing the answer modulo $998244353$.

Samples

3
1 2 3
1 2
2 3

166374060

Note

The tree in the example has six different connected subgraphs: ${1}, {2}, {3}, {1, 2}, {2, 3}, {1, 2, 3}$.

Their variance is $0, 0, 0,\frac{1}{4},\frac{1}{4},\frac{2}{3}$. So the answer is$\frac{7}{6}$, i.e. $7 × 6 ^{−1}$ mod $998244353 = 166374060$.