Barbarians

A country is made of $n$ islands joined by $n - 1$ bridges. For any two islands there is exactly one way to travel from one to the other without visiting any island twice.

Barbarians have attacked the country. They worked out that the bridges are the weak point, so they destroy the bridges one after another. The people of island $i$ start with anger $a_i$.

The anger changes like this. Take an island $x$. Let $a$ be the number of islands the people of $x$ can reach before some bridge is destroyed, and let $b$ be the number they can reach after it is destroyed. Both counts include island $x$ itself. The anger at island $x$ is then multiplied by $a - b + 1$.

You get $n - 1$ requests. Each request holds two integers $u$ and $v$. Let $res$ be the answer to the previous request, with $res = 0$ for the first request. The request destroys the bridge between island $u + res$ and island $v + res$.

Let $b_i$ be the anger at island $i$ after that bridge is destroyed. Set $res$ to $(b_1 + b_2 + \cdots + b_n)$ modulo $10^9 + 7$ and print that value.

The first example shows how the request format works. There are 5 islands and the starting anger is 1 2 3 4 5. The first request uses $res = 0$, so it destroys the bridge between islands 3 and 1. The anger at islands 1 and 2 is multiplied by 4 and the anger at the other three islands is multiplied by 3, so the anger becomes 4 8 9 12 15. The sum is 48, so $res$ becomes 48 and 48 is printed. The next request holds $-47$ and $-46$, so the bridge it destroys joins island $(-47) + 48 = 1$ and island $(-46) + 48 = 2$.

The first line contains the number of islands $n$ ($2 \le n \le 2 \times 10^5$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$, the starting anger ($1 \le a_i \le 10^9 + 6$).

Each of the next $n - 1$ lines contains two integers $u_i$ and $v_i$ describing a bridge ($1 \le u_i, v_i \le n$). It is guaranteed that there is exactly one way to travel between any two islands.

Each of the next $n - 1$ lines contains one request in the format described above. The bridge a request points to always exists and has not been destroyed yet, and both of its endpoints are between 1 and $n$.

For each request print the value of $res$, one per line, in the order of the requests.