Problem Statement

For an integer sequence $a=(a_1,a_2,\dots,a_n)$ of length $n$, its Kadomatsu degree is defined as the number of $i$ that are at least $2$ and less than $n$ and satisfy the following condition.

• At least one of "$a_i< a_{i+1}$ and $a_i< a_{i-1}$" or "$a_i> a_{i+1}$ and $a_i> a_{i-1}$" holds.

Here, the Kadomatsu degree of any integer sequence of length at most $2$ is defined to be $0$.

There is a simple connected undirected graph with $N$ vertices and $N-1$ edges. The vertices are numbered $1,2,\dots,N$, and the $i$-th edge connects vertex $U_i$ and vertex $V_i$ bidirectionally.

You are also given an integer sequence $A$ of length $N$.

Let $f(i,j)$ be the Kadomatsu degree of $q$, where $q=(A_{p_1},A_{p_2},\dots,A_{p_n})$ is obtained from the unique integer sequence $p=(p_1,p_2,\dots,p_n)$ of length $n$ satisfying all of the following conditions.

• $p_1=i$
• $p_n=j$
• $1\leq p_k\leq N(1\leq k\leq n)$
• All elements of $p$ are distinct.
• For every $k$ at least $1$ and less than $n$, vertex $p_k$ and vertex $p_{k+1}$ are directly connected by an edge.

Find $\sum_{i=1}^{N}\sum_{j=i}^{N}f(i,j)$ modulo $998244353$.

Input

$N$
$U_1\ V_1$
$U_2\ V_2$
$\vdots$
$U_{N-1}\ V_{N-1}$
$A_1\ A_2\ \dots\ A_N$

• $3\leq N\leq 2\times 10^5$
• $1\leq U_i,V_i\leq N(1\leq i\leq N-1)$
• The given graph is connected.
• $1\leq A_i\leq 10^9$

Output

Print the answer on $1$ line.

Sample

5
1 3
2 1
4 1
4 5
2 1 3 1 2

5

6
1 2
2 3
1 5
5 6
4 5
1 1 1 1 1 1

0

10
6 8
6 1
5 10
5 2
6 4
2 4
5 9
8 7
3 9
461924924 987491630 891274602 524053807 460183912 97638725 932784974 244569286 453506405 44117081

50