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 comment(linker, "/STACK:66777216")
using namespace std;
inline void add(int& a, int b) {
  a += b;
  if (a >= 1000000007) a -= 1000000007;
}
const int N = 100002;
int a, b, c, d, n, m, k;
vector<pair<int, int> > sm[N];
int cnt[N], sum[N], ss[N];
bool bad[N];
void dfsr(int v, int pr, int* cnt, int* sum, int* ss) {
  cnt[v] = 1;
  sum[v] = 0;
  ss[v] = 0;
  for (int _n(((int)((sm[v]).size())) - 1), i(0); i <= _n; i++) {
    int w = sm[v][i].first;
    if (w == pr || bad[w]) continue;
    dfsr(w, v, cnt, sum, ss);
    cnt[v] += cnt[w];
    add(sum[v], sum[w]);
    sum[v] = (sum[v] + (long long)cnt[w] * sm[v][i].second) % 1000000007;
    add(ss[v], ss[w]);
    ss[v] = (ss[v] + (long long)sm[v][i].second * sm[v][i].second % 1000000007 *
                         cnt[w]) %
            1000000007;
    ss[v] = (ss[v] + 2LL * sm[v][i].second * sum[w]) % 1000000007;
  }
}
int ovss[N], ovsum[N], sub[N];
int dfs_cnt(int v, int pr) {
  int ans = 1;
  for (int _n(((int)((sm[v]).size())) - 1), i(0); i <= _n; i++) {
    int w = sm[v][i].first;
    if (w == pr || bad[w]) continue;
    ans += dfs_cnt(w, v);
  }
  return ans;
}
pair<int, int> dfs_cen(int v, int pr, int ov) {
  pair<int, int> t = make_pair(1000000000, v);
  sub[v] = 1;
  int mx = 0;
  for (int _n(((int)((sm[v]).size())) - 1), i(0); i <= _n; i++) {
    int w = sm[v][i].first;
    if (w == pr || bad[w]) continue;
    pair<int, int> tt = dfs_cen(w, v, ov);
    t = min(t, tt);
    sub[v] += sub[w];
    mx = max(mx, sub[w]);
  }
  mx = max(mx, ov - sub[v]);
  t = min(t, make_pair(mx, v));
  return t;
}
int pcnt[N], psum[N], pss[N];
void dfs_part(int v, int pr, int sumsof, int cntrem, int sumrem, int sqrem) {
  ovsum[v] = (ovsum[v] + sumrem + (long long)sumsof * cntrem) % 1000000007;
  ovss[v] =
      (ovss[v] + sqrem + (long long)sumsof * sumsof % 1000000007 * cntrem +
       2LL * sumsof * sumrem) %
      1000000007;
  for (int _n(((int)((sm[v]).size())) - 1), i(0); i <= _n; i++) {
    int w = sm[v][i].first;
    if (w == pr || bad[w]) continue;
    dfs_part(w, v, (sumsof + sm[v][i].second) % 1000000007, cntrem, sumrem,
             sqrem);
  }
}
void rec(int s) {
  int ov = dfs_cnt(s, -1);
  pair<int, int> t = dfs_cen(s, -1, ov);
  s = t.second;
  dfsr(s, -1, pcnt, psum, pss);
  add(ovss[s], pss[s]);
  add(ovsum[s], psum[s]);
  for (int _n(((int)((sm[s]).size())) - 1), i(0); i <= _n; i++) {
    int w = sm[s][i].first;
    if (bad[w]) continue;
    int cntrem = pcnt[s] - pcnt[w];
    int sumrem =
        (psum[s] - psum[w] - (long long)sm[s][i].second * pcnt[w]) % 1000000007;
    if (sumrem < 0) sumrem += 1000000007;
    int sqrem =
        (pss[s] - pss[w] -
         (long long)sm[s][i].second * sm[s][i].second % 1000000007 * pcnt[w] -
         2LL * sm[s][i].second * psum[w]) %
        1000000007;
    if (sqrem < 0) sqrem += 1000000007;
    dfs_part(w, s, sm[s][i].second, cntrem, sumrem, sqrem);
  }
  bad[s] = 1;
  for (int _n(((int)((sm[s]).size())) - 1), i(0); i <= _n; i++) {
    int w = sm[s][i].first;
    if (bad[w]) continue;
    rec(w);
  }
}
int up[100002][18];
int tin[100002], tout[100002], ct;
int hg[100002];
void dfs_lca(int v, int p = 0) {
  tin[v] = ++ct;
  up[v][0] = p;
  for (int i = 1; i <= 17; ++i) up[v][i] = up[up[v][i - 1]][i - 1];
  for (size_t i = 0; i < sm[v].size(); ++i) {
    int to = sm[v][i].first;
    if (to != p) {
      hg[to] = (hg[v] + sm[v][i].second) % 1000000007;
      dfs_lca(to, v);
    }
  }
  tout[v] = ++ct;
}
bool upper(int a, int b) { return tin[a] <= tin[b] && tout[a] >= tout[b]; }
int lca(int a, int b) {
  if (upper(a, b)) return a;
  if (upper(b, a)) return b;
  for (int i = 17; i >= 0; --i)
    if (!upper(up[a][i], b)) a = up[a][i];
  return up[a][0];
}
int main() {
  scanf("%d", &n);
  for (int _n((n - 1) - 1), i(0); i <= _n; i++) {
    scanf("%d%d%d", &a, &b, &c);
    --a;
    --b;
    sm[a].push_back(make_pair(b, c));
    sm[b].push_back(make_pair(a, c));
  }
  dfsr(0, -1, cnt, sum, ss);
  rec(0);
  dfs_lca(0);
  scanf("%d", &m);
  for (int _n((m)-1), i(0); i <= _n; i++) {
    scanf("%d%d", &a, &b);
    --a;
    --b;
    int toall = ovss[a];
    int l = lca(a, b);
    int ans = 0, sub = 0;
    int len = (hg[a] - hg[l] + hg[b] - hg[l]) % 1000000007;
    if (len < 0) len += 1000000007;
    if (!upper(b, a)) {
      sub = (ss[b] + (long long)len * len % 1000000007 * cnt[b] +
             2LL * len * sum[b]) %
            1000000007;
    } else {
      int ssnd = ovss[b] - ss[b];
      if (ssnd < 0) ssnd += 1000000007;
      int snd = ovsum[b] - sum[b];
      if (snd < 0) snd += 1000000007;
      int cnd = n - cnt[b];
      sub = (ovss[a] - ssnd - (long long)len * len % 1000000007 * cnd -
             2LL * len * snd) %
            1000000007;
      if (sub < 0) sub += 1000000007;
    }
    ans = (2LL * sub - toall) % 1000000007;
    if (ans < 0) ans += 1000000007;
    printf("%d\n", ans);
  }
}
