题目描述

给定一棵 $n\ (1 \leq n\leq 10^5)$ 个顶点的带边权的树，以点 $1$ 为根。定义 $d(u,v)$ 为 $u$ 到 $v$ 的简单路径上所有边的权值之和。特别地，我们有 $d(u,u)=0$。

接着对节点 $v$ 定义集合 $S(v)$，表示所有满足 $d(1,u)=d(1,v)+d(v,u)$ 的点 $u$ 的集合。

函数 $f(u,v)$ 由下式定义：

$$f(u,v)=\sum_{x \in S(v)} d(u,x)^2-\sum_{x \notin S(v)} d(u,x)^2 $$

你的任务就是对于 $q$ 对 $u,v$ 计算出 $f(u,v)$ 的值。由于答案可能过大，请模 $10^9+7$ 输出。

输入格式

第一行一个整数 $n$，接下来 $n-1$ 行描述一棵树。

接下来一个整数 $q$，接下来 $q$ 行表示询问。

输出格式

对于每个询问，在一行中给出答案。

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

10
1000000005
1000000002
23
1000000002

8
1 2 100
1 3 20
2 4 2
2 5 1
3 6 1
3 7 2
6 8 5
6
1 8
2 3
5 8
2 6
4 7
6 1

999968753
49796
999961271
999991235
999958569
45130