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;
vector<pair<int, int> > E[100010];
int down[100010], vis[100010];
int n;
const int MOD = 1e9 + 7;
pair<int, int> S[100010];
pair<int, int> PP[100010];
void get_dfs(int x, int fa, int L, pair<int, int> &A) {
  down[x] = 1;
  A.first = (A.first + L) % MOD;
  A.second = (A.second + (long long)L * L) % MOD;
  for (auto e : E[x])
    if (e.second != fa && vis[e.second] == 0) {
      get_dfs(e.second, x, (L + e.first) % MOD, A);
      down[x] += down[e.second];
    }
}
void down_dfs(int x, int fa) {
  down[x] = 1;
  for (auto e : E[x])
    if (e.second != fa && vis[e.second] == 0) {
      down_dfs(e.second, x);
      down[x] += down[e.second];
    }
}
void put_dfs(int x, int fa, int L, pair<int, int> &A, int L0) {
  PP[x].second = (PP[x].second + A.second + A.first * 2LL * L +
                  ((long long)L * L) % MOD * L0) %
                 MOD;
  PP[x].first = (PP[x].first + A.first + (long long)L0 * L) % MOD;
  for (auto e : E[x])
    if (e.second != fa && vis[e.second] == 0) {
      put_dfs(e.second, x, (L + e.first) % MOD, A, L0);
    }
}
void Do(int x) {
  down_dfs(x, -1);
  int c = x, h = down[x] / 2;
  while (1) {
    int f = 0;
    for (auto e : E[c])
      if (vis[e.second] == 0 && down[e.second] < down[c] &&
          down[e.second] > h) {
        c = e.second;
        f = 1;
        break;
      }
    if (f == 0) break;
  }
  vector<int> near;
  vector<pair<int, int> > G;
  vector<int> lu;
  pair<int, int> tot = pair<int, int>(0, 0);
  int L0 = 1;
  for (auto e : E[c])
    if (!vis[e.second]) {
      near.push_back(e.second);
      pair<int, int> A = pair<int, int>(0, 0);
      get_dfs(e.second, c, e.first, A);
      G.push_back(A);
      lu.push_back(e.first);
      tot.first = (tot.first + A.first) % MOD;
      tot.second = (tot.second + A.second) % MOD;
      L0 += down[e.second];
    }
  for (int i = 0; i < (int)near.size(); i++) {
    int u = near[i];
    pair<int, int> A =
        pair<int, int>(tot.first - G[i].first, tot.second - G[i].second);
    if (A.first < 0) A.first += MOD;
    if (A.second < 0) A.second += MOD;
    put_dfs(u, c, lu[i], A, L0 - down[u]);
  }
  PP[c].second = (PP[c].second + tot.second) % MOD;
  PP[c].first = (PP[c].first + tot.first) % MOD;
  vis[c] = 1;
  for (int e : near) {
    Do(e);
  }
}
int dep[100010], ST[100010], EN[100010], ce;
int up[100010][20];
int Ldep[100010];
tuple<int, int, int> DP[100010];
void DFS(int x, int fa) {
  get<0>(DP[x]) = 1;
  ST[x] = ++ce;
  for (auto e : E[x])
    if (e.second != fa) {
      dep[e.second] = dep[x] + 1;
      Ldep[e.second] = (Ldep[x] + e.first) % MOD;
      up[e.second][0] = x;
      for (int i = 1; i < 20; i++)
        up[e.second][i] = up[up[e.second][i - 1]][i - 1];
      DFS(e.second, x);
      int L = e.first;
      int a0 = get<0>(DP[e.second]);
      int a1 = get<1>(DP[e.second]);
      int a2 = get<2>(DP[e.second]);
      get<0>(DP[x]) += a0;
      get<1>(DP[x]) = (a1 + get<1>(DP[x]) + (long long)L * a0) % MOD;
      get<2>(DP[x]) = (get<2>(DP[x]) + ((long long)L * L) % MOD * a0 +
                       (long long)2 * L * a1 + a2) %
                      MOD;
    }
  EN[x] = ce;
}
int lca(int x, int y) {
  if (dep[x] < dep[y]) swap(x, y);
  for (int i = 0; i < 20; i++)
    if (1 << i & (dep[x] - dep[y])) x = up[x][i];
  for (int i = 19; i >= 0; i--)
    if (up[x][i] != up[y][i]) x = up[x][i], y = up[y][i];
  return x == y ? x : up[x][0];
}
void solve() {
  scanf("%d", &n);
  for (int i = 0; i < n - 1; i++) {
    int x, y, z;
    scanf("%d%d%d", &x, &y, &z);
    E[x].push_back(pair<int, int>(z, y));
    E[y].push_back(pair<int, int>(z, x));
  }
  Do(1);
  DFS(1, -1);
  int q;
  scanf("%d", &q);
  while (q--) {
    int u, v;
    scanf("%d%d", &u, &v);
    if (ST[v] <= ST[u] && ST[u] <= EN[v]) {
      long long ans = PP[u].second;
      long long C = 0;
      long long a0 = n;
      long long a1 = PP[v].first;
      long long a2 = PP[v].second;
      a0 -= get<0>(DP[v]);
      a1 -= get<1>(DP[v]);
      a2 -= get<2>(DP[v]);
      long long L = Ldep[u] - Ldep[v];
      if (L < 0) L += MOD;
      C += (L * L) % MOD * a0;
      C += 2LL * L * a1;
      C += a2;
      ans -= 2 * C;
      ans %= MOD;
      if (ans < 0) ans += MOD;
      printf("%lld\n", ans);
    } else {
      long long ans = -PP[u].second;
      int a0 = get<0>(DP[v]);
      int a1 = get<1>(DP[v]);
      int a2 = get<2>(DP[v]);
      int lc = lca(u, v);
      long long L = Ldep[u] + Ldep[v] - 2LL * Ldep[lc];
      if (L < 0) L += MOD;
      ans += 2LL * (L * L) % MOD * a0;
      ans += 4LL * L * a1;
      ans += 2LL * a2;
      ans %= MOD;
      if (ans < 0) ans += MOD;
      printf("%lld\n", ans);
    }
  }
}
int main() {
  int Tc = 1;
  for (int tc = 1; tc <= Tc; tc++) {
    solve();
  }
  return 0;
}
