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>
#pragma warning(disable : 4996)
using namespace std;
int n, m;
vector<pair<int, int> > edge[200000];
struct INFO {
  long long depth;
  long long dis;
  long long child;
  long long down1, down2, up1, up2;
} d[200000];
int par[200000][20];
long long mod(long long x) {
  return (x % 1000000007 + 1000000007) % 1000000007;
}
void back(int now, int parent) {
  long long ccnt = 0, cnt1 = 0, cnt2 = 0;
  par[now][0] = parent == -1 ? now : parent;
  for (int i = 1; i < 20; i++) {
    par[now][i] = par[par[now][i - 1]][i - 1];
  }
  for (auto e : edge[now]) {
    if (e.first == parent) continue;
    d[e.first].depth = d[now].depth + 1;
    d[e.first].dis = d[now].dis + e.second;
    d[e.first].dis %= 1000000007;
    back(e.first, now);
    ccnt += d[e.first].child;
    ccnt %= 1000000007;
    cnt1 += d[e.first].down1 + d[e.first].child * e.second;
    cnt1 %= 1000000007;
    cnt2 += d[e.first].down2 + 2 * d[e.first].down1 * e.second;
    cnt2 %= 1000000007;
    cnt2 += d[e.first].child * e.second % 1000000007 * e.second;
    cnt2 %= 1000000007;
  }
  d[now].child = ccnt + 1;
  d[now].down1 = cnt1;
  d[now].down2 = cnt2;
}
void upback(int now, int parent, int dis) {
  if (parent != -1) {
    long long u = d[parent].up1 + d[parent].down1 -
                  (d[now].down1 + d[now].child * dis % 1000000007);
    d[now].up1 = u + dis * (n - d[now].child);
    d[now].up1 %= 1000000007;
    u = d[parent].up2 + d[parent].down2 -
        (d[now].down2 + 2 * d[now].down1 * dis % 1000000007 +
         d[now].child * dis % 1000000007 * dis % 1000000007);
    d[now].up2 = u +
                 2 * (d[now].up1 - dis * (n - d[now].child) % 1000000007) *
                     dis % 1000000007 +
                 (n - d[now].child) * dis % 1000000007 * dis % 1000000007;
    d[now].up2 %= 1000000007;
  }
  for (auto e : edge[now]) {
    if (e.first == parent) continue;
    upback(e.first, now, e.second);
  }
}
int getlca(int x, int y) {
  if (d[x].depth < d[y].depth) swap(x, y);
  int dis = d[x].depth - d[y].depth;
  int i, j;
  for (i = 0; i < 20; i++) {
    if (dis & (1 << i)) x = par[x][i];
  }
  if (x == y) return x;
  for (i = 19; i >= 0; i--) {
    if (par[x][i] != par[y][i]) x = par[x][i], y = par[y][i];
  }
  return par[x][0];
}
int main() {
  int i, j, k;
  scanf("%d", &n);
  for (i = 0; i < n - 1; i++) {
    int x, y, z;
    scanf("%d%d%d", &x, &y, &z), x--, y--;
    edge[x].push_back(pair<int, int>(y, z));
    edge[y].push_back(pair<int, int>(x, z));
  }
  back(0, -1);
  upback(0, -1, 0);
  scanf("%d", &m);
  for (i = 0; i < m; i++) {
    int x, y;
    scanf("%d%d", &x, &y), x--, y--;
    int lca = getlca(x, y);
    if (lca == y) {
      long long dis = d[x].dis - d[y].dis;
      long long u = d[y].up2 + 2 * dis * d[y].up1 % 1000000007 +
                    (n - d[y].child) * dis % 1000000007 * dis % 1000000007;
      long long dab = d[x].up2 + d[x].down2 - 2 * u;
      printf("%I64d\n", mod(dab));
    } else {
      long long dis = d[x].dis + d[y].dis - 2 * d[lca].dis;
      long long u = d[y].down2 + 2 * dis * d[y].down1 % 1000000007 +
                    d[y].child * dis % 1000000007 * dis % 1000000007;
      long long dab = 2 * u - d[x].down2 - d[x].up2;
      printf("%I64d\n", mod(dab));
    }
  }
  return 0;
}
