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;
inline int getint() {
  int c, l = 0, x;
  for (; !isdigit(c = getchar()); l = c)
    if (c == EOF) return 1 << 31;
  for (x = c - '0'; isdigit(c = getchar()); x = x * 10 + c - '0')
    if (c == EOF) break;
  return l == '-' ? -x : x;
}
int buf[100];
inline int putint(int x) {
  int i = 0;
  x = x < 0 ? putchar('-'), -x : x;
  for (; buf[i++] = x % 10, x; x /= 10)
    ;
  for (i = i - 1 ? i - 1 : 1; i--; putchar(buf[i] + '0'))
    ;
  putchar(10);
  return 1;
}
const int N = 200100;
const int mod = 1000000007;
int K, n, m, q, tp[N], sz[N], hc[N], fa[N], clk, ne[N * 2], to[N * 2],
    da[N * 2], G[N], xb;
long long dp[N], dg[N];
struct poly {
  int a[4];
  poly() { memset(a, 0, sizeof a); }
  poly operator+(const poly& b) {
    poly c;
    for (int i = 0; i <= K; i++) c.a[i] = (a[i] + b.a[i]) % mod;
    return c;
  }
  poly operator-(const poly& b) {
    poly c;
    for (int i = 0; i <= K; i++) c.a[i] = (a[i] - b.a[i] + mod) % mod;
    return c;
  }
  poly operator<<(const long long& tt) {
    long long t = (tt % mod + mod) % mod;
    poly c;
    for (int i = K; i >= 0; i--) {
      for (int j = K; j; j--) c.a[j] = (t * c.a[j] + c.a[j - 1]) % mod;
      c.a[0] = (t * c.a[0] + a[i]) % mod;
    }
    return c;
  }
  int operator()(const long long& x) {
    long long ans = 0, s = x % mod;
    for (int i = K; i >= 0; i--) ans = (ans * s + a[i]) % mod;
    return ans;
  }
} g[N], f[N];
void add(int x, int y, long long z) {
  ne[xb] = G[x];
  to[xb] = y;
  da[xb] = z;
  G[x] = xb++;
}
int lca(int x, int y) {
  for (; tp[x] != tp[y]; x = fa[tp[x]])
    if (dp[tp[x]] < dp[tp[y]]) swap(x, y);
  return dp[x] < dp[y] ? x : y;
}
int dfn[N], dft[N];
bool is(int x, int y) { return dfn[x] <= dfn[y] && dfn[y] <= dft[x]; }
long long dst(int x, int y) {
  int z = lca(x, y);
  return dp[x] + dp[y] - 2 * dp[z];
}
void dfs2(int x) {
  f[x].a[K] = 1;
  for (int i = G[x]; ~i; i = ne[i])
    if (to[i] != fa[x]) {
      int u = to[i], v = da[i];
      dp[u] = dp[x] + v;
      fa[u] = x;
      dfs2(u);
      f[x] = f[x] + (f[u] << v);
      sz[x] += sz[u];
      if (sz[u] > sz[hc[x]]) hc[x] = u;
    }
  if (!sz[x]) sz[x] = 1;
}
void dfs3(int x, int y) {
  for (int i = G[x]; ~i; i = ne[i])
    if (to[i] != fa[x]) {
      int u = to[i];
      g[u] = (f[x] << -dp[x]) - (f[u] << dp[u] - 2 * dp[x]) + g[x];
    }
  dfn[x] = ++clk;
  tp[x] = y;
  if (hc[x]) dfs3(hc[x], y);
  for (int i = G[x]; ~i; i = ne[i])
    if (!dfn[to[i]]) dfs3(to[i], to[i]);
  dft[x] = clk;
}
int calc(int u, int v) {
  if (is(u, v)) {
    poly a = g[v] - g[u];
    return (f[v](0) + a(dp[v])) % mod;
  } else {
    poly a = f[u];
    return a(dst(v, u));
  }
}
int main() {
  n = getint();
  K = 2;
  m = n - 1;
  memset(G, -1, sizeof G);
  for (int i = 1; i <= m; i++) {
    int x = getint(), y = getint(), z = getint();
    add(x, y, z);
    add(y, x, z);
  }
  dfs2(1);
  dfs3(1, 1);
  q = getint();
  while (q--) {
    int u, v;
    v = getint();
    u = getint();
    putint(((2 * calc(u, v) - calc(1, v)) % mod + mod) % mod);
  }
}
