408284: GYM103076 G Andre and the colorless tree

André is a person that loves trees... In his backyard, he has a plantation of several mystical and beautiful trees. But one tree stands out among the others ... The fruits of that tree are colorless.

This tree has $$$N$$$ fruits and each fruit is numbered from $$$0$$$ to $$$N-1$$$.

Each fruit connects to at least one other fruit through magical branches.

Initially, there are $$$N-1$$$ magical branches on the tree.

Since André finds the tree with colorless fruit unsightly, he decided to paint each fruit with a specific color.

However, every season of the year, there is a magical event in this tree, where each fruit later painted by André loses its color, and becomes colorless again. In addition, in this event, two fruits are temporarily connected, through a new magical branch. It is guaranteed that the first fruit is ancestor of the second fruit, considering the tree being rooted at the node 0. It is also guaranteed that these fruits are different. That connection is broken in the next season.

Since André is stubborn, he decides to paint the tree again each season. In each event, André has $$$Ki$$$ different colors at his disposal to paint the fruits of the tree, where $$$i$$$ is the index of each event. At each event, André wants to find out how many ways he can paint the tree, with the following condition: fruits connected by magical branches cannot have the same color. Since André is very busy playing Counter-Strike, he decided to ask for your help in calculating how many ways he can paint the fruits of the tree in the next $$$Q$$$ events.

Since there can be many ways to paint the tree, André is only interested in the remainder of the division of the quantity of ways to paint the tree by $$$1000000007$$$.

Be $$$X$$$ a node in a tree rooted on the node $$$R$$$, $$$Y$$$ is called ancestral of $$$X$$$, if $$$Y$$$ is contained in the path from $$$R$$$ to $$$X$$$.

An integer number $$$N$$$, indicating the number of fruits in the tree, followed by another integer $$$Q$$$, indicating the number of events. ($$$3 \le N, Q \le 10^5 $$$).

Then, $$$N-1$$$ lines, each line containing two integers, $$$U$$$ and $$$V$$$, indicating that exists a magical branch connecting fruit $$$U$$$ and fruit $$$V$$$( $$$0 \le U , V \le N-1$$$ ).

Then, $$$Q$$$ lines, where each line contains three integers: $$$U$$$, $$$V$$$, $$$K$$$, indicating that a new temporary magical branch will connect the fruits $$$U$$$ and $$$V$$$, and André has $$$K$$$ colors to paint the fruits of the tree ( $$$0 \le U , V \le N-1$$$ ) ( $$$3 \le K \le 10^9 $$$ ).

$$$Q$$$ lines, each line containing one integer, indicating the number of different ways André has to paint the fruits of the tree on each event, mod $$$1000000007$$$.

4 1
0 1
1 3
2 1
0 2 3

12

Before the first event, the colorless tree looks like this:

After the first event, the colorless tree looks temporarily like this: