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 NMAX = 1e5;
const int MOD = 1e9 + 7;
struct node_t {
  int sum;
  int sum2;
  int lazy;
  node_t operator+(const node_t &other) const {
    node_t ans;
    ans.sum = (this->sum + other.sum) % MOD;
    ans.sum2 = (this->sum2 + other.sum2) % MOD;
    ans.lazy = 0;
    return ans;
  }
  void add_val(int val, int st, int dr) {
    this->lazy = (this->lazy + val) % MOD;
    this->sum2 = (this->sum2 + 1LL * (1LL * val * val % MOD) * (dr - st + 1) +
                  2LL * val * this->sum) %
                 MOD;
    this->sum = (this->sum + 1LL * val * (dr - st + 1)) % MOD;
  }
};
node_t aint[4 * NMAX + 5];
int init_d[NMAX + 5];
int lin[NMAX + 5], len;
int fst[NMAX + 5];
int lst[NMAX + 5];
int n, q;
int ans[NMAX + 5];
vector<pair<int, int> > graph[NMAX + 5];
vector<pair<int, int> > queries[NMAX + 5];
void build(int nod, int st, int dr) {
  if (st == dr) {
    aint[nod].lazy = 0;
    aint[nod].sum = init_d[lin[st]];
    aint[nod].sum2 = 1LL * init_d[lin[st]] * init_d[lin[st]] % MOD;
    return;
  }
  int mid = (st + dr) / 2;
  build(nod * 2, st, mid);
  build(nod * 2 + 1, mid + 1, dr);
  aint[nod] = aint[2 * nod] + aint[2 * nod + 1];
}
void propag(int nod, int st, int dr) {
  if (st == dr || aint[nod].lazy == 0) {
    aint[nod].lazy = 0;
    return;
  }
  int mid = (st + dr) / 2;
  aint[nod * 2].add_val(aint[nod].lazy, st, mid);
  aint[nod * 2 + 1].add_val(aint[nod].lazy, mid + 1, dr);
  aint[nod].lazy = 0;
}
void update(int nod, int st, int dr, int S, int D, int val) {
  propag(nod, st, dr);
  if (dr < S || st > D) {
    return;
  }
  if (S <= st && dr <= D) {
    aint[nod].add_val(val, st, dr);
    return;
  }
  int mid = (st + dr) / 2;
  update(nod * 2, st, mid, S, D, val);
  update(nod * 2 + 1, mid + 1, dr, S, D, val);
  aint[nod] = aint[2 * nod] + aint[2 * nod + 1];
}
int query(int nod, int st, int dr, int S, int D) {
  propag(nod, st, dr);
  if (D < st || dr < S) {
    return 0;
  }
  if (S <= st && dr <= D) {
    return aint[nod].sum2;
  }
  int mid = (st + dr) / 2;
  return (query(nod * 2, st, mid, S, D) +
          query(nod * 2 + 1, mid + 1, dr, S, D)) %
         MOD;
}
void predfs(int nod, int tata, int dist) {
  init_d[nod] = dist;
  lin[++len] = nod;
  fst[nod] = len;
  for (auto it : graph[nod]) {
    if (it.first == tata) {
      continue;
    }
    predfs(it.first, nod, (dist + it.second) % MOD);
  }
  lst[nod] = len;
}
void dfs(int nod, int tata) {
  for (auto it : queries[nod]) {
    ans[it.second] = ((2 * query(1, 1, n, fst[it.first], lst[it.first]) -
                       query(1, 1, n, 1, n)) %
                          MOD +
                      MOD) %
                     MOD;
  }
  for (auto it : graph[nod]) {
    if (it.first == tata) {
      continue;
    }
    update(1, 1, n, 1, n, it.second);
    update(1, 1, n, fst[it.first], lst[it.first],
           (2 * MOD - 2 * it.second) % MOD);
    dfs(it.first, nod);
    update(1, 1, n, fst[it.first], lst[it.first], 2 * it.second % MOD);
    update(1, 1, n, 1, n, (MOD - it.second) % MOD);
  }
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i < n; i++) {
    int x, y, z;
    scanf("%d %d %d", &x, &y, &z);
    graph[x].push_back({y, z});
    graph[y].push_back({x, z});
  }
  predfs(1, 0, 0);
  build(1, 1, n);
  scanf("%d", &q);
  for (int i = 1; i <= q; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    queries[u].push_back({v, i});
  }
  dfs(1, 0);
  for (int i = 1; i <= q; i++) {
    printf("%d\n", ans[i]);
  }
  return 0;
}
