题目背景

此题读入量较大，请选择合适的读入方式。

题目描述

给你一棵 $n$ 个点的边带权有根树，根节点为编号为 $1$ 的节点。定义 $u$ 的 $k-son$ 为 $u$ 子树中深度（指经过边数）比 $u$ 恰好大 $k$ 的所有点。
$m$ 次询问求一个点 $u$ 的 $k-son$ 两两之间距离的和。你需要输出这个值 $\bmod\left(10^9+7\right)$ 的结果。

输入格式

第一行两个数 $n,m$。
接下来 $n-1$ 行每行三个数 $u,v,w$，代表 $u,v$ 之间有一条边权为 $w$ 的边。
接下来 $m$ 行每行两个数 $u,k$，代表一个询问。

输出格式

对于每个询问输出一行答案。

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

提示

样例 $1$ 解释

以下是样例中的树。

样例 $2$ 解释

以下是样例中的树。

数据范围

对于 $20\%$ 的数据，$n,m,k\le100$。
对于 $50\%$ 的数据，$n,m,k\le10^3$。
对于 $80\%$ 的数据，$n,m,k\le10^5$。
对于 $100\%$ 的数据，$1\le n,m,k\le10^6,1\le k\le n,1\le w\le10^5,1\le u,v\le n$，保证给出的是一棵树。