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.