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 = 1e5 + 5, mod = 1e9 + 7;
int zrb(int a, int b) { return (1LL * a * b % mod); }
int jm(int a, int b) {
  int tmp = (a + b) % mod;
  while (tmp < 0) tmp += mod;
  return (tmp);
}
int A[N], D[N << 2], SM[N << 2], SMLZ[N << 2], P[N], ST[N], FT[N], n, st, q,
    RT[N];
struct node {
  int x, id, c;
};
vector<node> ND[N];
void build(int id = 1, int l = 0, int r = n) {
  if (r - l < 2) {
    D[id] = zrb(A[l], A[l]);
    SM[id] = A[l];
    return;
  }
  int mid = ((l + r) >> 1);
  build((id << 1), l, mid);
  build((id << 1 | 1), mid, r);
  D[id] = jm(D[(id << 1)], D[(id << 1 | 1)]);
  SM[id] = jm(SM[(id << 1)], SM[(id << 1 | 1)]);
}
void shift(int id, int l, int r) {
  int ll = (id << 1), rr = (id << 1 | 1), mid = ((l + r) >> 1);
  D[ll] = jm(D[ll], zrb(2, zrb(SM[ll], SMLZ[id])));
  D[rr] = jm(D[rr], zrb(2, zrb(SM[rr], SMLZ[id])));
  D[ll] = jm(D[ll], zrb(mid - l, zrb(SMLZ[id], SMLZ[id])));
  D[rr] = jm(D[rr], zrb(r - mid, zrb(SMLZ[id], SMLZ[id])));
  SMLZ[ll] = jm(SMLZ[ll], SMLZ[id]);
  SMLZ[rr] = jm(SMLZ[rr], SMLZ[id]);
  SM[ll] = jm(SM[ll], zrb(mid - l, SMLZ[id]));
  SM[rr] = jm(SM[rr], zrb(r - mid, SMLZ[id]));
  SMLZ[id] = 0;
}
void add(int s, int e, int d, int id = 1, int l = 0, int r = n) {
  if (s >= e) return;
  if (l >= e || r <= s) return;
  if (l >= s && r <= e) {
    int ln = r - l;
    D[id] = jm(D[id], zrb(ln, zrb(d, d)));
    D[id] = jm(D[id], zrb(2, zrb(SM[id], d)));
    SM[id] = jm(SM[id], zrb(ln, d));
    SMLZ[id] = jm(SMLZ[id], d);
    return;
  }
  int mid = ((l + r) >> 1);
  shift(id, l, r);
  add(s, e, d, (id << 1), l, mid);
  add(s, e, d, (id << 1 | 1), mid, r);
  D[id] = jm(D[(id << 1)], D[(id << 1 | 1)]);
  SM[id] = jm(SM[(id << 1)], SM[(id << 1 | 1)]);
}
int get(int s, int e, int id = 1, int l = 0, int r = n) {
  if (s >= e) return (0);
  if (l >= e || r <= s) return (0);
  if (l >= s && r <= e) return (D[id]);
  int mid = ((l + r) >> 1);
  shift(id, l, r);
  return (jm(get(s, e, (id << 1), l, mid), get(s, e, (id << 1 | 1), mid, r)));
}
vector<pair<int, int> > adj[N];
void prDFS(int u, int p, int d = 0) {
  ST[u] = st;
  A[st++] = d;
  for (pair<int, int> x : adj[u])
    if (x.first ^ p) {
      P[x.first] = x.second;
      prDFS(x.first, u, jm(d, x.second));
    }
  FT[u] = st;
}
void DFS(int u, int p) {
  for (node nd : ND[u]) {
    if (!nd.c) {
      RT[nd.id] = jm(RT[nd.id], get(ST[nd.x], FT[nd.x]));
    } else {
      RT[nd.id] = jm(RT[nd.id], -D[1]);
      RT[nd.id] = jm(RT[nd.id], get(ST[nd.x], FT[nd.x]));
    }
  }
  for (pair<int, int> x : adj[u])
    if (x.first ^ p) {
      add(ST[x.first], FT[x.first], -x.second);
      add(0, ST[x.first], x.second);
      add(FT[x.first], n, x.second);
      DFS(x.first, u);
      add(ST[x.first], FT[x.first], x.second);
      add(0, ST[x.first], -x.second);
      add(FT[x.first], n, -x.second);
    }
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i < n; i++) {
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    adj[a].push_back({b, c});
    adj[b].push_back({a, c});
  }
  prDFS(1, 0);
  build();
  scanf("%d", &q);
  for (int Q = 0; Q < q; Q++) {
    int a, b;
    scanf("%d %d", &a, &b);
    node nd = {b, Q, 0};
    ND[a].push_back(nd);
    nd = {b, Q, 1};
    ND[a].push_back(nd);
  }
  DFS(1, 0);
  for (int i = 0; i < q; i++) printf("%d\n", RT[i]);
}
