territory

Due to her thirst for power, Sashka decided to create a new country. It will span across the territories of Bulgaria, which can be represented as a network of $N$ regions, numbered $1$ to $N$, connected by $N-1$ roads. From every region it is possible to reach every other region using the roads. Sashka’s country will span across several (one or more) regions such that they are connected. Regions are connected when there is a path between any two of the chosen regions on which no unchosen region lies.

The most recent census established that the $i$-th region has $a_i$ inhabitants. Thus, the population of Sashka’s country will be the sum of the individual populations of the chosen regions. Since it would be terribly boring for Sashka to consider just one variant of her country, she will consider all possible ones. She wants to find the sum of the populations over all possible choices of country. Write a program territory that finds this value. Since the sum may be too large, find its remainder when divided by $998 \ 244 \ 353$.

Input data

On one line of standard input the positive integer $N$ is given. On the next line $N$ positive integers $a_1, a_2, ..., a_N$ are given. On the remaining $N-1$ lines the road network is described: the $i$-th of these lines contains the integers $u_i$ and $v_i$, characterising a road between region $u_i$ and region $v_i$.

Output data

On standard output print the required value.

Constraints and clarifications

• $1 \leq N \leq 200 \ 000$
• $1 \leq a_i \leq 10^7$
• $1 \leq u_i, v_i \leq N$

Example 1

stdin

6
1 4 9 16 25 36
1 2
2 3
3 4
4 5
5 6

stdout

812

Explanation

Bulgaria is indicated in the image.

Example 2

stdin

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

stdout

864

Explanation

Bulgaria is indicated in the image.