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 N = 1e5 + 10;
const int MOD = 1e9 + 7;
struct segment {
  int l, r, to_add;
  pair<int, int> sum;
  int size() { return r - l; }
  int unity(int _l, int _r) { return max(0 * l, min(_r, r) - max(_l, l)); }
  segment(int _l = 0, int _r = 0) {
    l = _l;
    r = _r;
    sum = pair<int, int>(0, 0);
    to_add = 0;
  }
} seg[N << 2];
int n, h[N], lp[N], rp[N], ans[N];
vector<pair<int, int> > que[N], g[N];
vector<int> st;
int dfs(int, int = 0, int = 0, int = 0);
void build(int, int, int = 1);
void add(int, int, int = 1);
pair<int, int> get(int, int, int = 0, int = 1);
void update(int);
pair<int, int> get(int);
void answer(int, int = 0);
pair<int, int> calc(pair<int, int>, int, int);
pair<int, int> _pair_sum(pair<int, int>, pair<int, int>);
int _sum(int, int);
int _mul(int, int);
int _neg(int);
int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  for (int i = 1; i < n; i++) {
    int v, u, w;
    cin >> v >> u >> w;
    v--;
    u--;
    g[v].push_back({u, w});
    g[u].push_back({v, w});
  }
  dfs(0);
  build(0, n);
  int q;
  cin >> q;
  for (int i = 0; i < q; i++) {
    int v, u;
    cin >> v >> u;
    v--;
    u--;
    que[v].push_back({u, i});
  }
  answer(0);
  for (int i = 0; i < q; i++) cout << ans[i] << endl;
}
int dfs(int v, int pv, int d, int cur_pos) {
  h[v] = d;
  lp[v] = cur_pos;
  rp[v] = cur_pos + 1;
  st.push_back(v);
  for (auto [u, w] : g[v])
    if (u != pv) rp[v] = dfs(u, v, _sum(d, w), rp[v]);
  return rp[v];
}
void answer(int v, int pv) {
  int sigma_t = _neg(get(0).second);
  for (auto [u, query] : que[v])
    ans[query] = _sum(sigma_t, _mul(2, get(u).second));
  for (auto [u, w] : g[v])
    if (u != pv) {
      add(0, w);
      add(u, _mul(_neg(2), w));
      answer(u, v);
      add(u, _mul(2, w));
      add(0, _mul(_neg(1), w));
    }
}
void build(int l, int r, int v) {
  seg[v] = segment(l, r);
  if (r - l == 1) {
    seg[v].sum = {h[st[l]], _mul(h[st[l]], h[st[l]])};
    return;
  }
  int med = (l + r) / 2;
  build(l, med, v << 1);
  build(med, r, v << 1 | 1);
  update(v);
}
void add(int ver, int val, int v) {
  int l = lp[ver];
  int r = rp[ver];
  if (seg[v].unity(l, r) == 0) return;
  if (seg[v].unity(l, r) == seg[v].size()) {
    seg[v].to_add = _sum(seg[v].to_add, val);
    seg[v].sum = calc(seg[v].sum, seg[v].size(), val);
    return;
  }
  add(ver, val, v << 1);
  add(ver, val, v << 1 | 1);
  update(v);
  seg[v].sum = calc(seg[v].sum, seg[v].size(), seg[v].to_add);
}
pair<int, int> get(int ver) { return get(lp[ver], rp[ver]); }
pair<int, int> get(int l, int r, int par_sum, int v) {
  if (seg[v].unity(l, r) == 0) return pair<int, int>(0, 0);
  if (seg[v].unity(l, r) == seg[v].size())
    return calc(seg[v].sum, seg[v].size(), par_sum);
  pair<int, int> lc = get(l, r, _sum(par_sum, seg[v].to_add), v << 1);
  pair<int, int> rc = get(l, r, _sum(par_sum, seg[v].to_add), v << 1 | 1);
  return _pair_sum(lc, rc);
}
void update(int v) {
  seg[v].sum = _pair_sum(seg[v << 1].sum, seg[v << 1 | 1].sum);
}
pair<int, int> calc(pair<int, int> v, int cnt, int d) {
  auto [A, B] = v;
  int C = _mul(d, cnt);
  int sum_1 = _sum(A, C);
  int sum_2 = _sum(_sum(B, _mul(d, C)), _mul(_mul(2, d), A));
  return pair<int, int>(sum_1, sum_2);
}
int _sum(int a, int b) {
  a += b;
  if (a >= MOD) a -= MOD;
  return a;
}
int _mul(int a, int b) { return 1LL * a * b % MOD; }
int _neg(int x) {
  return MOD - x;
  x = -x;
  while (x < 0) x += MOD;
  return x;
}
pair<int, int> _pair_sum(pair<int, int> a, pair<int, int> b) {
  return pair<int, int>(_sum(a.first, b.first), _sum(a.second, b.second));
}
