K-Son Distance Sum on a Weighted Rooted Tree

You are given a weighted rooted tree with n nodes, where the root is node 1. Each edge has an associated weight. For any node u, define its k-son as all nodes in the subtree of u whose depth (i.e. the number of edges from u) is exactly k more than that of u. There are m queries. In each query, given a node u and an integer k, you are to compute the sum of pairwise distances between every two distinct nodes in the set of u's k-sons. Output the answer modulo \(10^9+7\).

The distance between two nodes x and y is defined as the sum of the weights on the unique simple path between them. Note that if the k-son set has fewer than two nodes, the answer is 0.

Note: In this problem, when k = 0, the only node in the "0-son" set is u itself.

inputFormat

The input begins with two integers n and m (n is the number of nodes and m is the number of queries).

Then follow n-1 lines, each containing three integers u, v and w indicating an edge from node u to node v with weight w. It is guaranteed that the tree is rooted at node 1.

Then follow m lines, each containing two integers u and k representing a query.

outputFormat

For each query, output one integer: the sum of pairwise distances between all distinct nodes in the k-son set of u, taken modulo \(10^9+7\).

sample

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

5
11
4