Ladrão de Frutas

Pedrinho está encrencado! Ele precisa comprar um presente para sua namorada, mas, ele está sem dinheiro. Como ele abandonou seus amigos, e não pode pedir dinheiro para eles, decidiu que, para poder comprar o presente, vai vender as frutas da árvore mágica do seu Zé . A árvore mágica do seu Zé possui $N$ nós e cada um deles possui uma fruta de valor $V_i$. Para roubar as frutas, Pedrinho faz um caminho simples (cada vértice no caminho aparece uma única vez) de um vértice $u_1$ até outro $u_m$ e pega as frutas nos nós do caminho. Como a árvore é mágica, ela muda o valor total das frutas que Pedrinho pegou de acordo com o caminho que ele faz. Para um dado caminho simples que começa em $u_1$ e acaba em $u_m$, a função valor $Val(u_1,u_m)$, que determina quanto Pedrinho ganha fazendo esse caminho, é definida como $Val(u_1,u_m) = \sum_{i=1}^{m} (-1)^{i+1}\times V_{u_i}$. Perceba que pode ser que $u_1 = u_m$.

Pedrinho quer saber qual que é a soma da função $Val$ de todos os caminhos diferentes possíveis e ele pediu a sua ajuda. Dois caminhos são diferentes se os vértices onde ele começa são diferentes ou se os vértices onde ele termina são diferentes. Os caminhos de $1$ a $5$ e de $5$ a $1$, por exemplo, são diferentes, já que os vértices de início são distintos.

Como esse total pode ser muito grande, imprima ele módulo $10^9 + 7$.

Input

A primeira linha contém $N$($2\leq N\leq 2 \times 10^5$) - o número de nós na árvore.

A segunda linha contém $N$ inteiros espaçados: $V_1,V_2,V_3,$ ... $V_N$ ($-10^9 \leq V_i \leq 10^9$) - o valor da fruta de cada nó.

As próximas $N - 1$ linhas possuem dois inteiros $u$ e $v$, indicando que há uma aresta entre os nós $u$ e $v$.

Output

Imprima a soma das funções $Val$ de todos os caminhos simples distintos módulo $10^9 + 7$.

Exemplos:

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

40

8
-2 6 -4 -4 -9 -3 -7 23
8 2
2 3
1 4
6 5
7 6
4 7
5 8

4

No exemplo 1, perceba que:

$Val(1,2) = -4 - (1) =-5$

$Val(3,4) = 5 - (-4)+(-2) = 7$

Somando a função $Val$ de todos os caminhos possíveis nesse exemplo, temos que a soma é 40.

Para submeter o problema, utilize esse link.