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;
int readint() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
struct node {
  long long s, ms, lazy;
} t[300000];
const int cys = 1000000007;
int n, m, tot, cnt;
int v[200005], nxt[200005], c[200005], h[100005], rnk[100005], dfn[100005],
    siz[100005], ans[100005], dep[100005];
vector<pair<int, int> > q[100005];
int mod(int x) { return x >= cys ? x - cys : x; }
void addedge(int x, int y, int z) {
  v[++tot] = y;
  c[tot] = z;
  nxt[tot] = h[x];
  h[x] = tot;
  v[++tot] = x;
  c[tot] = z;
  nxt[tot] = h[y];
  h[y] = tot;
}
void update(int id) {
  t[id].s = mod(t[id << 1].s + t[id << 1 | 1].s);
  t[id].ms = mod(t[id << 1].ms + t[id << 1 | 1].ms);
}
void build(int id, int l, int r) {
  if (l == r) {
    t[id].s = dep[rnk[l]], t[id].ms = 1ll * dep[rnk[l]] * dep[rnk[l]] % cys;
    return;
  }
  int mid = (l + r) / 2;
  build(id << 1, l, mid);
  build(id << 1 | 1, mid + 1, r);
  update(id);
}
void pushdown(int id, int l, int r) {
  if (t[id].lazy) {
    int mid = (l + r) / 2;
    t[id << 1].lazy = mod(t[id << 1].lazy + t[id].lazy),
            t[id << 1 | 1].lazy = mod(t[id << 1 | 1].lazy + t[id].lazy);
    t[id << 1].ms = mod(mod(t[id << 1].ms + 1ll * (mid - l + 1) * t[id].lazy %
                                                cys * t[id].lazy % cys) +
                        2ll * t[id].lazy * t[id << 1].s % cys);
    t[id << 1 | 1].ms =
        mod(mod(t[id << 1 | 1].ms +
                1ll * (r - mid) * t[id].lazy % cys * t[id].lazy % cys) +
            2ll * t[id].lazy * t[id << 1 | 1].s % cys);
    t[id << 1].s = mod(t[id << 1].s + 1ll * t[id].lazy * (mid - l + 1) % cys),
            t[id << 1 | 1].s =
                mod(t[id << 1 | 1].s + 1ll * t[id].lazy * (r - mid) % cys);
    t[id].lazy = 0;
  }
}
void change(int id, int l, int r, int ql, int qr, int c) {
  if (l == ql && r == qr) {
    t[id].lazy = mod(t[id].lazy + c);
    t[id].ms = mod(mod(t[id].ms + 1ll * (r - l + 1) * c % cys * c % cys) +
                   2ll * c * t[id].s % cys);
    t[id].s = mod(t[id].s + 1ll * c * (r - l + 1) % cys);
    return;
  }
  pushdown(id, l, r);
  int mid = (l + r) / 2;
  if (qr <= mid)
    change(id << 1, l, mid, ql, qr, c);
  else if (ql > mid)
    change(id << 1 | 1, mid + 1, r, ql, qr, c);
  else
    change(id << 1, l, mid, ql, mid, c),
        change(id << 1 | 1, mid + 1, r, mid + 1, qr, c);
  update(id);
}
int query(int id, int l, int r, int ql, int qr) {
  if (l == ql && r == qr) return t[id].ms;
  pushdown(id, l, r);
  int mid = (l + r) / 2;
  if (qr <= mid)
    return query(id << 1, l, mid, ql, qr);
  else if (ql > mid)
    return query(id << 1 | 1, mid + 1, r, ql, qr);
  else
    return mod(query(id << 1, l, mid, ql, mid) +
               query(id << 1 | 1, mid + 1, r, mid + 1, qr));
}
void dfs1(int u, int fa) {
  dfn[u] = ++cnt, rnk[cnt] = u, siz[u] = 1;
  for (int p = h[u]; p; p = nxt[p]) {
    if (v[p] == fa) continue;
    dep[v[p]] = mod(dep[u] + c[p]);
    dfs1(v[p], u);
    siz[u] += siz[v[p]];
  }
}
void dfs2(int u, int fa) {
  for (int i = 0; i < q[u].size(); i++)
    ans[q[u][i].second] =
        mod(mod(2 * query(1, 1, n, dfn[q[u][i].first],
                          dfn[q[u][i].first] + siz[q[u][i].first] - 1)) +
            cys - t[1].ms);
  for (int p = h[u]; p; p = nxt[p]) {
    if (v[p] == fa) continue;
    change(1, 1, n, 1, n, c[p]);
    change(1, 1, n, dfn[v[p]], dfn[v[p]] + siz[v[p]] - 1,
           mod(2 * (cys - c[p])));
    dfs2(v[p], u);
    change(1, 1, n, 1, n, cys - c[p]);
    change(1, 1, n, dfn[v[p]], dfn[v[p]] + siz[v[p]] - 1, mod(2 * c[p]));
  }
}
int main() {
  n = readint();
  int x, y, z;
  for (int i = 1; i <= n - 1; i++) {
    x = readint();
    y = readint();
    z = readint();
    addedge(x, y, z);
  }
  dfs1(1, -1);
  build(1, 1, n);
  m = readint();
  for (int i = 1; i <= m; i++) {
    x = readint();
    y = readint();
    q[x].push_back(make_pair(y, i));
  }
  dfs2(1, -1);
  for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
  return 0;
}
