Ali is Hamed's little brother and tomorrow is his birthday. Hamed wants his brother to earn his gift so he gave him a hard programming problem and told him if he can successfully solve it, he'll get him a brand new laptop. Ali is not yet a very talented programmer like Hamed and although he usually doesn't cheat but this time is an exception. It's about a brand new laptop. So he decided to secretly seek help from you. Please solve this problem for Ali. 

An n-vertex weighted rooted tree is given. Vertex number 1 is a root of the tree. We define d(u, v) as the sum of edges weights on the shortest path between vertices u and v. Specifically we define d(u, u) = 0. Also let's define S(v) for each vertex v as a set containing all vertices u such that d(1, u) = d(1, v) + d(v, u). Function f(u, v) is then defined using the following formula:

<image>

The goal is to calculate f(u, v) for each of the q given pair of vertices. As the answer can be rather large it's enough to print it modulo 109 + 7.

Input

In the first line of input an integer n (1 ≤ n ≤ 105), number of vertices of the tree is given.

In each of the next n - 1 lines three space-separated integers ai, bi, ci (1 ≤ ai, bi ≤ n, 1 ≤ ci ≤ 109) are given indicating an edge between ai and bi with weight equal to ci.

In the next line an integer q (1 ≤ q ≤ 105), number of vertex pairs, is given.

In each of the next q lines two space-separated integers ui, vi (1 ≤ ui, vi ≤ n) are given meaning that you must calculate f(ui, vi).

It is guaranteed that the given edges form a tree.

Output

Output q lines. In the i-th line print the value of f(ui, vi) modulo 109 + 7.

Examples

Input

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


Output

10
1000000005
1000000002
23
1000000002


Input

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


Output

999968753
49796
999961271
999991235
999958569
45130
#include <bits/stdc++.h>
using namespace std;
const int N = 100005, LG = 18, Mod = 1e9 + 7;
int n, q, ts, sz[N], st[N], en[N], H[N], P[N][LG];
long long D[N], dp[N], sum[N], dp2[N], sum2[N];
vector<pair<int, long long> > Adj[N];
inline int Fix(long long a) {
  a %= Mod;
  if (a < 0) a += Mod;
  return (a);
}
void DFS(int v, int p) {
  P[v][0] = p;
  sz[v] = 1;
  st[v] = ts++;
  for (int i = 1; i < LG; i++) P[v][i] = P[P[v][i - 1]][i - 1];
  for (auto &u : Adj[v])
    if (u.first != p) {
      H[u.first] = H[v] + 1;
      D[u.first] = (D[v] + u.second) % Mod;
      DFS(u.first, v);
      sz[v] += sz[u.first];
      sum[v] = Fix(sum[v] + sum[u.first] + sz[u.first] * u.second);
      dp[v] += Fix(dp[u.first] + u.second * u.second % Mod * sz[u.first] % Mod);
      dp[v] = Fix(dp[v] + sum[u.first] * u.second * 2);
    }
  en[v] = ts;
}
void DFS2(int v, int p) {
  for (auto &u : Adj[v])
    if (u.first != p) {
      sum2[u.first] = Fix(sum2[v] + sum[v] - sum[u.first] -
                          u.second * (sz[u.first] * 2 - n));
      dp2[u.first] = Fix(dp2[v] + dp[v] - dp[u.first] -
                         u.second * u.second % Mod * sz[u.first]);
      dp2[u.first] += Fix(sum[u.first] * u.second * (-2) % Mod +
                          u.second * u.second % Mod * (n - sz[u.first]));
      dp2[u.first] += Fix(
          u.second *
          Fix(sum2[v] + sum[v] - sum[u.first] - sz[u.first] * u.second) * 2);
      dp2[u.first] = Fix(dp2[u.first]);
      DFS2(u.first, v);
    }
}
inline int LCA(int v, int u) {
  if (H[v] < H[u]) return (LCA(u, v));
  for (int i = LG - 1; ~i; i--)
    if ((H[v] - H[u]) & (1 << i)) v = P[v][i];
  if (v == u) return (v);
  for (int i = LG - 1; ~i; i--)
    if (P[v][i] != P[u][i]) v = P[v][i], u = P[u][i];
  return (P[v][0]);
}
inline int Dist(int v, int u) { return Fix(D[v] + D[u] - D[LCA(u, v)] * 2); }
inline bool Sub(int v, int u) { return (st[u] <= st[v] && en[v] <= en[u]); }
int main() {
  scanf("%d", &n);
  for (int i = 1, v, u, w; i < n; i++)
    scanf("%d%d%d", &v, &u, &w), Adj[v].push_back({u, w}),
        Adj[u].push_back({v, w});
  DFS(1, 0);
  DFS2(1, 0);
  scanf("%d", &q);
  for (; q; q--) {
    int v, u;
    scanf("%d%d", &u, &v);
    long long tot = 0, d = Dist(u, v);
    if (Sub(u, v) && u != v) {
      tot = dp2[v] + d * d % Mod * (n - sz[v]);
      tot = Fix(tot + sum2[v] * d * 2);
      printf("%d\n", Fix(dp[u] + dp2[u] - tot * 2));
    } else {
      tot = dp[v] + d * d % Mod * sz[v];
      tot = Fix(tot + d * sum[v] * 2);
      printf("%d\n", Fix(tot * 2 - dp[u] - dp2[u]));
    }
  }
  return (0);
}
