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.

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:

- All snow is removed from that road.
- 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.

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.

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)$.

**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_{1} = 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} = 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_{3} = 2 + 4 cm of snow and no new snow falls, so the final state is (4, 1, 0, 0).*

*The output is (1 ⋅ y_{1} + 2 ⋅ y_{2} + 3 ⋅ y_{3})=3 + 4 + 18 = 25.*