Description

You are given a rooted tree with $n$ nodes and weighted edges. The root is node $1$. Define the $k$-son of a node $u$ as all nodes in the subtree of $u$ whose depth (number of edges on the path) is exactly $k$ greater than that of $u$.
There are $m$ queries. For each query, compute the sum of distances between every pair of nodes among the $k$-sons of a node $u$. You need to output the result modulo $\bmod\left(10^9+7\right)$.

Input Format

The first line contains two integers $n, m$.
The next $n - 1$ lines each contain three integers $u, v, w$, indicating that there is an edge of weight $w$ between $u$ and $v$.
The next $m$ lines each contain two integers $u, k$, indicating a query.

Output Format

For each query, output one line containing the answer.

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

3
3
3

10 5
1 2 1
1 3 3
2 4 2
2 5 2
3 6 3
3 7 1
5 8 2
6 9 1
6 10 3
1 2
3 2
6 1
1 3
2 2

40
4
4
30
0

Hint

Sample $1$ Explanation

Below is the tree in the sample.

Sample $2$ Explanation

Below is the tree in the sample.

Constraints

For $20\%$ of the testdata, $n, m, k \le 100$.
For $50\%$ of the testdata, $n, m, k \le 10^3$.
For $80\%$ of the testdata, $n, m, k \le 10^5$.
For $100\%$ of the testdata, $1 \le n, m, k \le 10^6$, $1 \le k \le n$, $1 \le w \le 10^5$, $1 \le u, v \le n$. It is guaranteed that the given graph is a tree.

Translated by ChatGPT 5