Province A has a total of $n$ cities, connected by $n-1$ roads to form a tree.

Each city $i$ has a non-negative integer charm value $w_i$. A connected subgraph $S$ of cities is called harmonious if the average of the charm values of the cities in $S$ is $1$, i.e., $\frac 1{|S|} \sum_{u\in S} w_u = 1$.

We do not know the specific charm value of each city; we only know that the charm value of city $i$ is an integer chosen uniformly at random from $0$ to $a_i$.

Calculate the expected number of harmonious connected subgraphs in Province A. You only need to output the answer multiplied by $\prod_{i=1}^n (a_i+1)$. Since the answer may be very large, output the result modulo $998244353$.

Input

The first line contains a positive integer $n$, representing the number of cities.

The second line contains $n$ positive integers, representing $a_i$ in order.

The next $n-1$ lines each contain two positive integers $u, v$, representing an edge.

Output

Output a single integer representing the answer.

Examples

Input 1

2
1 2
1 2

Output 1

7

Note 1

• When $w_1=1$, $\{1\}$ is harmonious, which occurs with probability $\frac 12$.
• When $w_2=1$, $\{2\}$ is harmonious, which occurs with probability $\frac 13$.
• When $w_1=w_2=1$ or $w_1=0, w_2=2$, $\{1, 2\}$ is harmonious, which occurs with probability $\frac 13$.

Therefore, the total expected number of harmonious connected subgraphs is $\frac 12 + \frac 13 + \frac 13 = \frac 76$.

Input 2

3
2 1 3
1 2
1 3

Output 2

46

Constraints

For $100\%$ of the data, $1\le n\le 3000$. For all $1\le i\le n$, $1\le a_i\le n$. The input $u, v$ is guaranteed to form a tree.

For test cases $1\sim 3$, $n\le 50$.

For test cases $4\sim 5$, $\sum a_i \le 5000$.

For test cases $6\sim 7$, the tree is a chain, and $v=u+1$.

For test case $8$, $a_i=n$.

For test cases $9\sim 10$, there are no special constraints.