問題文

青木くんは 頂点$1,2,...,N$ からなる木 $T$ を手に入れました。$T$ の各頂点$i$ には値$i$ が既に書き込まれています。
青木くんは木 $T$を根付き木とみなして遊ぶことにしました。

青木くんは根付き木に対して、「頂点$i$ に、頂点$i$の(自分を除く)どの先祖の値よりも大きな値が書き込まれている」とき、頂点$i$ を神童と呼ぶことに決めました。但し根は必ず神童であるとします。
また $N$頂点のうち、いくつが神童であるかを神童数と定義しました。
(各頂点が神童かどうかは、どの頂点を根とするかに依存することに注意して下さい)
例えば下図のような根付き木を考えると、黄色の頂点が神童であり、神童数は4となります。
ここで $6$の値が書き込まれた頂点は神童です。なぜなら先祖に$\{3,1\}$の値が書き込まれており、$6$未満の値しか含まれないからです。
また $4$の値が書き込まれた頂点は神童ではありません。なぜなら先祖に$\{3,7\}$の値が書き込まれており、$4$よりも大きな値が含まれるからです。

青木くんは$T$の神童数が根の取り方に依存することに気づき、
頂点$i (i=1,2,...,N)$を根としたときの神童数$S_i$がいくつになるのか、あなたに尋ねてきました。
たくさんの数を伝えるのは大変なので、数列$r=\{r_1,r_2,...,r_N\}$を用いて、$(r_1+S_1)\times(r_2+S_2)\times ...\times(r_N+S_N)$ を教えてあげることにしました。
但しこの値は非常に大きくなりうるので、$10^9+7$で割った余りを教えてあげて下さい。

入力

$N$ 
$r_1\ r_2\ ...\ r_N$
$u_1\ v_1$
$u_2\ v_2$
$\vdots$
$u_{N-1}\ v_{N-1}$

１行目に木の頂点数$N$が与えられます。
２行目には答えの計算に用いる数列$r$の$N$要素が空白区切りで与えられます。
３行目から$N+1$行目までには、木$T$ の辺の端点を表す整数 $u, v$ が空白区切りで与えられます。これは頂点$u, v$が双方向に結ばれていることを意味します。
※入力が多めなので注意して下さい。

制約

• $1 \le N \le 2\times 10^5$
• $0 \le r_i \lt 10^9+7$
• $1 \le u_i,v_i \le N$
• 入力されるグラフは$N$頂点の木である。
• 入力は全て整数である。

出力

$\prod_{i=1}^N(r_i+S_i)$ を$10^9+7$で割った余りを一行に出力して下さい。
最後に改行して下さい。

サンプル

サンプル1

入力

3
0 0 0
1 2
2 3

出力

6

頂点1,2,3を根とみなした様子が以下の図です。黄色に塗られた頂点が神童です。

サンプル2

入力

3
0 0 0
1 3
3 2

出力

4

頂点1,2,3を根とみなした様子が以下の図です。黄色に塗られた頂点が神童です。

20
397391841 679700971 145606697 977415091 513786611 99670444 666370425 151199845 823785563 113697511 311512752 592551093 141690528 337950684 441783513 543190271 462296398 851050627 141769971 473127767
17 19
18 11
19 6
20 8
8 16
20 3
13 9
11 10
15 8
11 20
17 18
14 8
1 20
2 5
11 7
11 4
5 20
1 12
2 13

598344873