暂无测试数据。

小 C 给你一棵 $n$ 个点的树，每条边 $<x_i,y_i>$ 有一个权值 $w_i$。

令 $S$ 为 $u\to v$ 链上的点集。当 $u,v$ 间由第 $i$ 条边直接相连时，$u,v$ 间的距离 $dis(u,v)=w_i$，否则

$$\displaystyle dis(u,v)=\frac{\sum_{i,j\in S,\{i,j\}\neq\{u,v\}}dis(i,j)}{2}$$

现在有 $q$ 次询问，每次询问两点间的距离，由于答案可能很大，请输出它对 $10^9+7$ 取模的值。

输入格式

输入共 $(n+q+1)$ 行。

第一行为一个正整数 $n$，表示树的点的个数。

接下来 $(n-1)$ 行，每行三个数 $x_i,y_i,w_i$，表示一条树边。

第 $(n+1)$ 行为一个正整数 $q$，表示询问次数。

接下来 $q$ 行，每行两个数 $u,v$，代表查询 $u,v$ 间的距离 $dis(u,v)$。

输出格式

对于每次询问，输出一个数表示答案。

数据规模与约定

对于 $30\%$ 的数据，$1 \leq n,q \leq 100$；

对于 $100\%$ 的数据，满足 $1\le n,q \leq 2000$，$1\le x_i,y_i\le n$，$1\le w_i<10^9+7$。

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

1
10