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 mod = (int)1e9 + 7;
struct hashInt {
  int x;
  hashInt() {}
  hashInt(int _x) : x(_x) {}
  inline hashInt operator+(const hashInt &y) const {
    int z = x + y.x;
    if (z >= mod) z -= mod;
    if (z < 0) z += mod;
    return hashInt(z);
  }
  inline hashInt operator-(const hashInt &y) const {
    int z = x - y.x;
    if (z >= mod) z -= mod;
    if (z < 0) z += mod;
    return hashInt(z);
  }
  inline hashInt operator*(const hashInt &y) const {
    return hashInt((long long)x * y.x % mod);
  }
};
struct edge {
  int next, node;
  hashInt w;
} e[100100 << 1 | 1];
int head[100100 + 1], tot = 0;
inline void addedge(int a, int b, int w) {
  e[++tot].next = head[a];
  head[a] = tot, e[tot].node = b, e[tot].w = w;
}
struct DP {
  hashInt sum, sqr;
  DP() {}
  DP(int _s, int _q) : sum(_s), sqr(_q) {}
  DP(hashInt _s, hashInt _q) : sum(_s), sqr(_q) {}
} up[100100 + 1], down[100100 + 1], downex[100100 + 1];
int n, size[100100 + 1], q;
inline hashInt delta(const DP &x, int n, hashInt b) {
  return x.sqr + b * b * n + b * 2 * x.sum;
}
void preUp(int x, int f) {
  size[x] = 1, up[x].sum = up[x].sqr = 0;
  for (int i = head[x]; i; i = e[i].next) {
    int node = e[i].node;
    if (node == f) continue;
    preUp(node, x);
    size[x] += size[node];
    up[x].sum = up[x].sum + up[node].sum + e[i].w * size[node];
    up[x].sqr = up[x].sqr + delta(up[node], size[node], e[i].w);
  }
}
void preDown(int x, int f) {
  for (int i = head[x]; i; i = e[i].next) {
    int node = e[i].node;
    if (node == f) continue;
    DP cur;
    cur.sum = down[x].sum + up[x].sum - up[node].sum - e[i].w * size[node];
    cur.sqr = down[x].sqr + up[x].sqr - delta(up[node], size[node], e[i].w);
    downex[node] = cur;
    down[node].sum = cur.sum + e[i].w * (n - size[node]);
    down[node].sqr = delta(cur, n - size[node], e[i].w);
    preDown(node, x);
  }
}
int p[18 + 1][100100 + 1], logn, dep[100100 + 1];
hashInt dis[100100 + 1];
void preDA(int x, int f) {
  p[0][x] = f;
  for (int i = head[x]; i; i = e[i].next) {
    int node = e[i].node;
    if (node == f) continue;
    dep[node] = dep[x] + 1;
    dis[node] = dis[x] + e[i].w;
    preDA(node, x);
  }
}
inline int LCA(int x, int y) {
  if (dep[x] > dep[y]) swap(x, y);
  for (int i = logn; i >= 0; --i)
    if (dep[x] <= dep[p[i][y]]) y = p[i][y];
  if (x == y) return x;
  for (int i = logn; i >= 0; --i)
    if (p[i][x] != p[i][y]) x = p[i][x], y = p[i][y];
  return p[0][x];
}
int main(int argc, char *argv[]) {
  scanf("%d", &n);
  for (int i = 1; i < n; ++i) {
    int x, y, w;
    scanf("%d%d%d", &x, &y, &w);
    addedge(x, y, w), addedge(y, x, w);
  }
  preUp(1, 0);
  preDown(1, 0);
  dep[1] = 1, preDA(1, 0);
  logn = (int)(log((double)n) / log(2.0));
  for (int i = 1; i <= logn; ++i)
    for (int j = 1; j <= n; ++j) p[i][j] = p[i - 1][p[i - 1][j]];
  scanf("%d", &q);
  while (q--) {
    int x, y;
    scanf("%d%d", &x, &y);
    int p = LCA(x, y);
    hashInt d = dis[x] + dis[y] - dis[p] * 2;
    hashInt ans = 0;
    if (p == y) {
      ans = delta(down[y], n - size[y], d);
      ans = up[x].sqr + down[x].sqr - ans * 2;
    } else {
      ans = delta(up[y], size[y], d);
      ans = ans * 2 - up[x].sqr - down[x].sqr;
    }
    printf("%d\n", ans.x);
  }
  fclose(stdin);
  fclose(stdout);
  return 0;
}
