408764: GYM103295 L Space Tourism

Galesa and her group of fellow lovable misfits, together known as the Saviours of the Solar System, are attempting to make a little extra profit by shuttling groups of paying customers between locations in the star system.

Travel in the star system is heavily regulated by the Galactic Council, so Galesa and her crew cannot travel arbitrarily between the $$$n$$$ locations in the star system. Rather, the available paths between the $$$n$$$ locations form a tree, so there is a unique path that Galesa must take between every two distinct locations.

Each of the $$$n$$$ locations have an associated enjoyment value $$$e_i$$$, which gives the amount of overall enjoyment that Saviours of the Solar System derive from traveling that location $$$i$$$. The overall enjoyment of traveling between two locations $$$i$$$ and $$$j$$$ is the product of all the enjoyment values for each location on the path between locations $$$i$$$ and $$$j$$$. Note that the Saviours of the Solar System still derive enjoyment from staying at a single location and only collecting the $$$e_i$$$ for that location, so this would still count as a path.

Given that Galesa and the Saviours of the Solar System are going to be going on a lot of these trips, they want to calculate the overall enjoyment that they'll experience. Therefore, they want you to calculate the sum of the enjoyment values for each possible path that they could take throughout the star system. Because this value is large, output the answer mod $$$10^9 + 7$$$.

The first line consists of a single integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$. The next line consists of $$$n$$$ integers $$$e_i$$$ $$$(1 \leq e_i \leq 10^5)$$$, which gives the enjoyment value for each of the $$$i$$$ locations in the star system. The next $$$n - 1$$$ lines consist of two integers $$$u_i, v_i$$$ $$$1 \leq u_i, v_i \leq n$$$, which indicates that Galesa can travel between locations $$$u_i$$$ and $$$v_i$$$.

Output a single integer giving the sum of the enjoyment values for each possible path that Galesa and the Saviours of the Solar System could take throughout the star system mod $$$10^9 + 7$$$

3
5 2 3
1 2
1 3

65

5
5 2 3 4 6
1 2
1 3
2 4
3 5

1251

For the first sample, there are paths with overall enjoyment $$$5, 2, 3, 10, 15, 30$$$, which together sum to $$$65$$$.