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 long long maxn = 1e5 + 100;
const long long mod = 1e9 + 7;
long long sum1[maxn], sum2[maxn], size[maxn];
long long dfn[maxn], dfncnt, f[maxn][20], d[maxn][20], n, dep[maxn];
vector<long long> side[maxn], w[maxn];
long long trans(long long u, long long val) {
  return (sum2[u] + size[u] * val % mod * val % mod + 2 * val * sum1[u] % mod) %
         mod;
}
void dfs1(long long u, long long fa) {
  f[u][0] = fa;
  dfn[u] = ++dfncnt;
  size[u] = 1;
  dep[u] = dep[fa] + 1;
  for (long long i = 0; i < side[u].size(); i++) {
    long long v = side[u][i];
    if (v == fa) continue;
    dfs1(v, u);
    size[u] += size[v];
    d[v][0] = w[u][i];
    sum1[u] = (sum1[u] + sum1[v] + w[u][i] * size[v] % mod) % mod;
    sum2[u] = (sum2[u] + trans(v, w[u][i])) % mod;
  }
}
void init() {
  for (long long i = (1), iend = (19); i <= iend; i++)
    for (long long j = (1), jend = (n); j <= jend; j++)
      f[j][i] = f[f[j][i - 1]][i - 1];
  for (long long i = (1), iend = (19); i <= iend; i++)
    for (long long j = (1), jend = (n); j <= jend; j++)
      d[j][i] = (d[j][i - 1] + d[f[j][i - 1]][i - 1]) % mod;
}
long long get_dis(long long u, long long v) {
  long long ans = 0;
  if (dep[u] < dep[v]) swap(u, v);
  for (long long i = 19; i >= 0; i--)
    if (dep[f[u][i]] >= dep[v]) ans = (ans + d[u][i]) % mod, u = f[u][i];
  if (u == v) return ans;
  for (long long i = 19; i >= 0; i--)
    if (f[u][i] != f[v][i])
      ans = (1ll * ans + d[u][i] + d[v][i]) % mod, u = f[u][i], v = f[v][i];
  return (1ll * ans + d[u][0] + d[v][0]) % mod;
}
struct Query {
  long long u, v, idx;
  bool insubtree;
} q[maxn];
long long ans[maxn];
bool cmp(Query a, Query b) { return dfn[a.u] < dfn[b.u]; }
long long now = 1, t;
void dfs2(long long u, long long fa) {
  while (now <= t && q[now].u == u) {
    long long v = q[now].v, idx = q[now].idx;
    if (q[now].insubtree) {
      ans[idx] = (sum2[u] - 2 * trans(f[v][0], get_dis(f[v][0], u))) % mod;
      ans[idx] = (ans[idx] + mod) % mod;
    } else {
      ans[idx] = (2 * trans(v, get_dis(u, v)) - sum2[u]) % mod;
      ans[idx] = (ans[idx] + mod) % mod;
    }
    now++;
  }
  for (long long i = 0; i < side[u].size(); i++) {
    long long v = side[u][i];
    if (v == fa) continue;
    long long bku1 = sum1[u], bku2 = sum2[u], bku3 = size[u];
    long long bkv1 = sum1[v], bkv2 = sum2[v], bkv3 = size[v];
    long long tmp1 = trans(v, w[u][i]),
              tmp2 = trans(u, w[u][i]) - trans(v, 2 * w[u][i]);
    tmp2 = (tmp2 % mod + mod) % mod;
    sum1[u] = (bku1 - (bkv1 + w[u][i] * bkv3) % mod) % mod;
    sum1[u] = (sum1[u] % mod + mod) % mod;
    sum1[v] = ((bku1 - (bkv1 + w[u][i] * bkv3) % mod) +
               (bku3 - bkv3) * w[u][i] % mod + bkv1) %
              mod;
    sum1[v] = (sum1[v] % mod + mod) % mod;
    sum2[u] = (bku2 - tmp1) % mod;
    sum2[u] = (sum2[u] % mod + mod) % mod;
    sum2[v] = tmp2 + bkv2;
    sum2[v] = (sum2[v] % mod + mod) % mod;
    size[u] = bku3 - bkv3;
    size[v] = bku3;
    dfs2(v, u);
    sum1[u] = bku1, sum2[u] = bku2, size[u] = bku3;
    sum1[v] = bkv1, sum2[v] = bkv2, size[v] = bkv3;
  }
}
signed main() {
  ios::sync_with_stdio(0);
  cin >> n;
  for (long long i = (1), iend = (n - 1); i <= iend; i++) {
    long long u, v, val;
    cin >> u >> v >> val;
    side[u].push_back(v);
    w[u].push_back(val);
    side[v].push_back(u);
    w[v].push_back(val);
  }
  dfs1(1, 0);
  init();
  cin >> t;
  for (long long i = (1), iend = (t); i <= iend; i++) {
    cin >> q[i].u >> q[i].v;
    q[i].idx = i;
    if (dfn[q[i].v] <= dfn[q[i].u] &&
        dfn[q[i].u] <= dfn[q[i].v] + size[q[i].v] - 1)
      q[i].insubtree = 1;
  }
  sort(q + 1, q + 1 + t, cmp);
  dfs2(1, 0);
  for (long long i = (1), iend = (t); i <= iend; i++) {
    cout << (ans[i] % mod + mod) % mod << endl;
  }
  return 0;
}
