Internet Problem Solving Contest

• Easy input data set – H1 (generator)
• Hard input data set – H2 (generator)

Your town has been hit by an enormous amount of snow this winter. The town council has decided to buy a snow plow to clear the roads.

Problem specification

The town has n intersections, numbered 1 through n. These are all connected together by a network of n − 1 bidirectional roads. (In other words, the road network is a tree.) All roads have the same length.

At the beginning of winter, there was no snow anywhere. During the winter the snow plow made q journeys. For each journey, we know the path the plow travelled and whether it was snowing during that journey.

During each journey the plow travelled along the only simple path from the origin to the destination of the journey. If it did snow, it always snowed during the entire journey, and it always snowed in the entire town, not just on the plow’s path. All snowfall during the entire winter happened during some of the plow’s journeys.

Whenever the plow travels through a road, two things happen in order:

1. All snow is removed from that road.
2. If it’s snowing, every road in the town (including the one just cleaned) gains 1 cm of snow.

The destination of one journey might not be equal to the starting point of the next one. In that case, the snow plow isn’t active in the meantime – it moves to the next starting point without changing the amount of snow on the roads.

For each journey, compute the total amount of snow the plow removed during that journey.

Input specification

The first line of the input file contains an integer t specifying the number of test cases. Each test case is preceded by a blank line.

Each test case starts with a line containing the integers n and q (1 ≤ n ≤ 10 000 000; 1 ≤ q ≤ 25 000 000). The next n − 1 lines contain integers p_i, q_i (1 ≤ p_i, q_i ≤ n) meaning that intersections p_i and q_i are connected by a road. The i-th of the following q lines contains integers a_i, b_i, c_i (1 ≤ a_i, b_i ≤ n; 0 ≤ c_i ≤ 1) describing the i-th journey of the snow plow: The journey started at intersection a_i and ended at intersection b_i. We have c_i = 1 if it snowed during this journey, and c_i = 0 if it did not.

In the easy subproblem H1 it is guaranteed that there is a road between intersections i and i + 1 for every 1 ≤ i < n. (The road network is a line.)

Because the size of h1.in is about 800 MB and the size of h2.in is about 1.2 GB, you cannot download them directly. Instead, we have provided small Python 2 programs h1gen.py and h2gen.py that will generate h1.in and h2.in when executed. Each generator should take under 10 minutes to run on average hardware. We recommend running them early – for example, starting them as you start working on your solution for this problem.

Output specification

For each test case: For i = 1, …, q, let y_i be the total amount of snow removed during journey i, and let z_i be i ⋅ y_i. Output one line with a single number: $(z_1 + \cdots + z_q) \bmod (10^9 + 7)$.

Example

Input:

1

5 3
1 2
2 3
3 4
3 5
1 4 1
3 2 1
4 5 0

Output:

25

During the journey from 1 to 4, the plow removed y₁ = 0 + 1 + 2 = 3 cm of snow. Afterwards, the roads have (3, 2, 1, 3) cm (in the order from the input). During the second journey, we remove y₂ = 2 cm of snow from the 2 − 3 road, and then every road gains another 1 cm, with final amounts (4, 1, 2, 4). In the third journey, we remove y₃ = 2 + 4 cm of snow and no new snow falls, so the final state is (4, 1, 0, 0).

The output is (1 ⋅ y₁ + 2 ⋅ y₂ + 3 ⋅ y₃)=3 + 4 + 18 = 25.