問題文

長さ $n$ の整数列 $a=(a_1,a_2,\dots,a_n)$ について、門松度を以下の条件を満たす $2$ 以上 $n$ 未満の $i$ の個数と定義します。

• 「 $a_i< a_{i+1}$ かつ $a_i< a_{i-1}$」または「 $a_i> a_{i+1}$ かつ $a_i> a_{i-1}$」の少なくとも一方が成り立つ

ただし、長さ $2$ 以下の任意の整数列の門松度は $0$ であるとします。

$N$ 頂点 $N-1$ 辺の単純連結無向グラフがあります。頂点には $1,2,\dots,N$ と番号がついており、$i$ 番目の辺は頂点 $U_i$ と頂点 $V_i$ を双方向に結びます。

また、長さ $N$ の整数列 $A$ が与えられます。

$f(i,j)$ を、以下の条件をすべて満たす長さ $n$ の唯一の整数列 $p=(p_1,p_2,\dots,p_n)$ から $q=(A_{p_1},A_{p_2},\dots,A_{p_n})$ を得たときの、$q$ の門松度とします。

• $p_1=i$
• $p_n=j$
• $1\leq p_k\leq N(1\leq k\leq n)$
• $p$ のすべての要素は相違なる
• $1$ 以上 $n$ 未満のすべての $k$ について、頂点 $p_k$ と頂点 $p_{k+1}$ は直接辺で結ばれている

$\sum_{i=1}^{N}\sum_{j=i}^{N}f(i,j)$ を $998244353$ で割った余りを求めてください。

入力

$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)$
• 与えられるグラフは連結である。
• $1\leq A_i\leq 10^9$

出力

$1$ 行で、答えを出力してください。

サンプル

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