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 MOD = 1000 * 1000 * 1000 + 7;
const int MAX_N = 100 * 1000 + 10;
const int LOG = 20 + 5;
vector<pair<int, int>> adj[MAX_N];
int dp1[MAX_N], dp2[MAX_N];
int dp3[MAX_N], dp4[MAX_N];
int par[MAX_N][LOG];
int cmp[MAX_N], n;
int dis[MAX_N];
int h[MAX_N];
long long mul(long long a, long long b) {
  a %= MOD, b %= MOD;
  return a * b % MOD;
}
long long change(long long n) { return (n % MOD + MOD) % MOD; }
void dfs1(int u = 0, int dad = 0) {
  par[u][0] = dad, cmp[u] = 1;
  for (int i = 1; i < LOG; i++) par[u][i] = par[par[u][i - 1]][i - 1];
  for (auto x : adj[u])
    if (x.first != dad) {
      int v = x.first, w = x.second;
      h[v] = h[u] + 1, dis[v] = change(dis[u] + w), dfs1(v, u);
      cmp[u] += cmp[v];
      dp1[u] = change(dp1[u] + dp1[v] + mul(cmp[v], w));
      dp2[u] =
          change(dp2[u] + dp2[v] + mul(cmp[v], mul(w, w)) + mul(2 * dp1[v], w));
    }
}
void dfs2(int u = 0, int dad = 0, int w = 0) {
  dp3[u] = change(dp3[dad] + mul(n - 2 * cmp[u], w));
  dp4[u] = change(dp4[dad] + mul(n, mul(w, w)) +
                  mul(dp3[dad] - 2 * (dp1[u] + mul(cmp[u], w)), 2 * w));
  for (auto x : adj[u])
    if (x.first != dad) dfs2(x.first, u, x.second);
}
int get_par(int u, int k) {
  for (int i = 0; i < LOG; i++)
    if (k >> i & 1) u = par[u][i];
  return u;
}
int lca(int u, int v) {
  if (h[u] > h[v]) swap(u, v);
  v = get_par(v, h[v] - h[u]);
  if (u == v) return u;
  for (int i = LOG - 1; ~i; i--)
    if (par[u][i] != par[v][i]) u = par[u][i], v = par[v][i];
  return par[u][0];
}
int F(int u, int v) {
  int x = lca(u, v);
  int d = change(dis[u] + dis[v] - 2 * dis[x]);
  if (x != v)
    return change(2 * (dp2[v] + mul(cmp[v], mul(d, d)) + mul(dp1[v], 2 * d)) -
                  dp4[u]);
  return change(dp4[u] - 2 * (dp4[v] - dp2[v] + mul(n - cmp[v], mul(d, d)) +
                              mul(dp3[v] - dp1[v], 2 * d)));
}
int main() {
  ios_base ::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  cin >> n;
  for (int i = 1; i < n; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    u--, v--;
    adj[u].push_back({v, w});
    adj[v].push_back({u, w});
  }
  dfs1(), dp3[0] = dp1[0], dp4[0] = dp2[0], dfs2();
  int q;
  cin >> q;
  while (q--) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    cout << F(u, v) << endl;
  }
  return 0;
}
