该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

With the passage of time, Fls's birthday is coming. R0 has a special gift for Fls. We all know that Fls likes cats very much, so R0 bought a lot of cat dolls to form a big string.

R0 doesn't like to do useless things, so there won't be extra lines, but it can ensure that all the dolls are strung together. There are a total of $n$ dolls, each with a number of $1, 2, ..., n$. Because each cat doll has its own characteristics, R0 has a liking value for each cat doll.

After he prepared the gift, he suddenly find that Tiny-Weiwei's birthday is coming also. Fortunately, he think that he could cut out two strings of dolls (In other words, it has to be cut twice. Bacause R0 picks up No.1 doll, the two doll strings for gifts should be the parts dropped after cutting. That is to say, you can't choose the string containing the doll No.1.) and give them to them respectively, so he carries $No.1$ doll and begins to cut it. It is also mentioned above that R0 does not like to do useless things, so if you can get the sum of these two doll strings by cutting them once or less (It's not the sum of the values), it will only be considered as a string.

You can know that the happy value of a person's doll string is the sum of R0 liking value for each cat doll. R0 wants both of them to be happy as much as possible, so he wants to know theFls'happiness $\times$ Tiny-Weiwei's happiness, what is the maximum.

输入格式

The first line contains a single integer $t$ —— the number of test cases.

Then the descriptions of $t$ test cases follow.

The first line of each test case contains one integers $n$ $(3 \leq n \leq 10^{6})$.

The next line contains $n$ integers, $a_1, a_2, ..., a_n$ $(-10^7 \leq a_i \leq 10^{7})$.

The next $(n- 1)$ lines, each line contains two numbers.

The $i$-th of these lines contains integers $x_i$ and $y_i$.

—— $x_i$ and $y_i$ are tied together with a rope ($1 \leq x_i, y_i \leq n$).

Ensure that the $\sum{n} \leq 10^6$, and the length with 1 as the endpoint does not exceed $10^{4}$.

输出格式

For each test case, print an integer, the answer mod $10^9+7$.

样例

3
3
4 2 3
1 2
1 3
3
4 2 -3
1 2
1 3 
10
0 -19 -71 24 18 39 19 -84 6 99
7 3
2 5
2 6
9 7
10 1
8 4
10 2
5 9
4 3

6
1000000001
999997667

提示

In the first example,

If you choose a string of point 2, the other string is point 1 and point 3.

Because if you not cut, you can also get point 2 and (point1 + point3).

So, you can only choose a string of point2, the other string is point 3.

In the third example,

Through these cutting methods, the two doll strings in the graph are legal.

Through these cutting methods, the two doll strings in the graph are illegal.