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 MAXn = 1e5 + 10, MAXx = 4 * MAXn, MOD = 1e9 + 7;
long long n, q, st[MAXn], ft[MAXn], now, h[MAXn], ans[MAXn];
vector<pair<long long, long long> > g[MAXn], query[MAXn];
struct node {
  int l, r, lc, rc;
  long long lazy;
  pair<long long, long long> val;
  node() {
    lazy = l = r = lc = rc = 0;
    val = pair<long long, long long>(0, 0);
  }
  void id(int v) {
    lc = 2 * v;
    rc = 2 * v + 1;
  }
  int size() { return r - l; }
  bool leaf() { return size() == 1; }
  bool unity(int lq, int rq) { return max(l, lq) < min(r, rq); }
  int unitys(int lq, int rq) { return min(r, rq) - max(l, lq); }
  bool init(int lq, int rq) { return lq <= l && r <= rq; }
};
node seg[MAXx];
inline pair<long long, long long> merge(pair<long long, long long> p1,
                                        long long k, long long cnt) {
  k %= MOD;
  p1.first %= MOD;
  p1.second %= MOD;
  return pair<long long, long long>(
      (((p1.first + ((((k * k) % MOD) * cnt) % MOD)) % MOD) +
       ((((2 * k) % MOD) * p1.second) % MOD) + MOD) %
          MOD,
      (p1.second + ((k * cnt) % MOD) + MOD) % MOD);
}
void build(int v, int l, int r) {
  seg[v].id(v);
  seg[v].l = l;
  seg[v].r = r;
  if (seg[v].leaf()) {
    seg[v].val.first = (h[seg[v].l] * h[seg[v].l]) % MOD;
    seg[v].val.second = h[seg[v].l];
    return;
  }
  int med = (l + r) / 2;
  build(seg[v].lc, l, med);
  build(seg[v].rc, med, r);
  seg[v].val.first = seg[seg[v].lc].val.first + seg[seg[v].rc].val.first;
  seg[v].val.second = seg[seg[v].lc].val.second + seg[seg[v].rc].val.second;
}
void add(int v, int l, int r, long long k) {
  if (!seg[v].unity(l, r)) return;
  if (seg[v].init(l, r)) {
    seg[v].lazy += k + MOD;
    seg[v].lazy %= MOD;
    seg[v].val = merge(seg[v].val, k, seg[v].size());
    return;
  }
  add(seg[v].lc, l, r, k);
  add(seg[v].rc, l, r, k);
  seg[v].val.first = seg[seg[v].lc].val.first + seg[seg[v].rc].val.first;
  seg[v].val.second = seg[seg[v].lc].val.second + seg[seg[v].rc].val.second;
  seg[v].val = merge(seg[v].val, seg[v].lazy, seg[v].size());
}
pair<long long, long long> get(int v, int l, int r) {
  if (!seg[v].unity(l, r)) return pair<long long, long long>(0, 0);
  if (seg[v].init(l, r)) {
    return seg[v].val;
  }
  pair<long long, long long> hp1 = get(seg[v].lc, l, r),
                             hp2 = get(seg[v].rc, l, r);
  pair<long long, long long> res = pair<long long, long long>(
      (hp1.first + hp2.first) % MOD, (hp1.second + hp2.second) % MOD);
  res = merge(res, seg[v].lazy, seg[v].unitys(l, r));
  return res;
}
void dfs(int v, int par, long long hi) {
  st[v] = now++;
  h[st[v]] = hi;
  for (int i = 0; i < g[v].size(); i++)
    if (g[v][i].first != par)
      dfs(g[v][i].first, v, (hi + g[v][i].second) % MOD);
  ft[v] = now;
}
void dfsans(int v, int par) {
  for (int i = 0; i < query[v].size(); i++) {
    int ind = query[v][i].second, node = query[v][i].first;
    ans[ind] -= (get(1, 0, now).first + MOD) % MOD;
    ans[ind] = (ans[ind] + MOD) % MOD;
    ans[ind] += (2 * get(1, st[node], ft[node]).first) % MOD;
    ans[ind] = (ans[ind] + MOD) % MOD;
  }
  for (int i = 0; i < g[v].size(); i++) {
    long long node = g[v][i].first, weight = g[v][i].second;
    if (node != par) {
      add(1, 0, st[node], weight);
      add(1, st[node], ft[node], (MOD - weight));
      add(1, ft[node], now, weight);
      dfsans(node, v);
      add(1, ft[node], now, (MOD - weight));
      add(1, st[node], ft[node], weight);
      add(1, 0, st[node], (MOD - weight));
    }
  }
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n;
  for (int i = 0; i < n - 1; i++) {
    int u, v, c;
    cin >> u >> v >> c;
    g[u].push_back(pair<long long, long long>(v, c));
    g[v].push_back(pair<long long, long long>(u, c));
  }
  cin >> q;
  for (int i = 0; i < q; i++) {
    int u, v;
    cin >> u >> v;
    query[u].push_back(pair<long long, long long>(v, i));
  }
  dfs(1, 0, 0);
  build(1, 0, now);
  dfsans(1, 0);
  for (int i = 0; i < q; i++) cout << ans[i] << '\n';
}
