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
import java.io.*;
import java.util.*;

public class D {

	BufferedReader br;
	PrintWriter out;
	StringTokenizer st;
	boolean eof;

	static final int LOG = 17;
	static final int P = 1_000_000_007;

	static class Edge {
		int to, cost;

		public Edge(int to, int cost) {
			this.to = to;
			this.cost = cost;
		}

	}

	List<Edge>[] g;

	int n;

	int[][] up;
	int[] tIn, tOut;
	int[] depth;
	int[] sz;
	int time = 0;

	int[] sDown, sAll;
	int[] s2Down, s2All;

	void dfs1(int v, int p) {
		sz[v] = 1;
		tIn[v] = time++;
		up[v][0] = p == -1 ? 0 : p;
		for (Edge e : g[v]) {
			if (e.to == p) {
				continue;
			}
			depth[e.to] = (depth[v] + e.cost) % P;
			dfs1(e.to, v);
			sz[v] += sz[e.to];

			sDown[v] += (int) (((long) e.cost * sz[e.to] + sDown[e.to]) % P);
			sDown[v] %= P;

			s2Down[v] += (int) (((long) e.cost * e.cost % P * sz[e.to] % P + 2L
					* e.cost * sDown[e.to] % P + s2Down[e.to]) % P);
			s2Down[v] %= P;

		}
		tOut[v] = time;
	}

	void dfs2(int v, int p) {
		for (Edge e : g[v]) {
			if (e.to == p) {
				continue;
			}
			int mult = ((n - 2 * sz[e.to]) % P + P) % P;
			sAll[e.to] = (int) (((long) mult * e.cost % P + sAll[v]) % P);

			s2All[e.to] = s2All[v];
			long mult2 = sAll[v] - 2L
					* (sDown[e.to] + (long) sz[e.to] * e.cost % P) % P;
			if (mult2 < 0) {
				mult2 += P;
			}
			s2All[e.to] += (int) (2L * e.cost * mult2 % P);
			s2All[e.to] %= P;

			s2All[e.to] += (int) ((long) n * e.cost % P * e.cost % P);
			s2All[e.to] %= P;
			dfs2(e.to, v);

		}
	}

	boolean isAnc(int v1, int v2) {
		return tIn[v1] <= tIn[v2] && tOut[v2] <= tOut[v1];
	}

	int lca(int v1, int v2) {
		if (isAnc(v1, v2)) {
			return v1;
		}
		if (isAnc(v2, v1)) {
			return v2;
		}
		for (int i = LOG - 1; i >= 0; i--) {
			int to = up[v2][i];
			if (!isAnc(to, v1)) {
				v2 = to;
			}
		}
		return up[v2][0];
	}

	void solve() throws IOException {
		n = nextInt();
		g = new List[n];
		for (int i = 0; i < n; i++) {
			g[i] = new ArrayList<>();
		}
		for (int i = 0; i < n - 1; i++) {
			int v1 = nextInt() - 1;
			int v2 = nextInt() - 1;
			int len = nextInt();
			g[v1].add(new Edge(v2, len));
			g[v2].add(new Edge(v1, len));
		}

		up = new int[n][LOG];
		tIn = new int[n];
		tOut = new int[n];
		depth = new int[n];

		sDown = new int[n];
		sAll = new int[n];
		s2Down = new int[n];
		s2All = new int[n];
		sz = new int[n];
		dfs1(0, -1);

		sAll[0] = sDown[0];
		s2All[0] = s2Down[0];

		dfs2(0, -1);

		// System.err.println(Arrays.toString(sDown));
		// System.err.println(Arrays.toString(sAll));
		// System.err.println(Arrays.toString(s2Down));
		// System.err.println(Arrays.toString(s2All));

		for (int i = 1; i < LOG; i++)
			for (int j = 0; j < n; j++) {
				up[j][i] = up[up[j][i - 1]][i - 1];
			}

		int q = nextInt();
		while (q-- > 0) {
			int u = nextInt() - 1;
			int v = nextInt() - 1;
			long ret;
			if (isAnc(v, u)) {

				long dvu = depth[u] - depth[v];
				if (dvu < 0) {
					dvu += P;
				}
				ret = dvu * dvu % P * (n - sz[v]) % P;
				int sDv = (sAll[v] - sDown[v]);
				if (sDv < 0) {
					sDv += P;
				}
				ret += 2L * dvu % P * sDv % P;
				ret %= P;

				long s2Dv = s2All[v] - s2Down[v];
				if (s2Dv < 0) {
					s2Dv += P;
				}
				ret += s2Dv;
				ret %= P;
				ret = s2All[u] - 2L * ret % P;
				if (ret < 0) {
					ret += P;
				}

			} else {
				int l = lca(v, u);
				long dvu = (long) depth[v] + depth[u] - 2L * depth[l];
				dvu = (dvu % P + P) % P;

				ret = dvu * dvu % P * sz[v] % P;
				if (ret < 0) {
					ret += P;
				}

				int sDv = sDown[v];
				ret += 2L * dvu % P * sDv % P;
				ret %= P;

				long s2Dv = s2Down[v];
				ret += s2Dv;
				ret %= P;

				// System.err.println(ret);

				ret = 2L * ret % P - s2All[u];

				if (ret < 0) {
					ret += P;
				}
			}
			out.println(ret);
		}
	}

	D() throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		solve();
		out.close();
	}

	public static void main(String[] args) throws IOException {
		new D();
	}

	String nextToken() {
		while (st == null || !st.hasMoreTokens()) {
			try {
				st = new StringTokenizer(br.readLine());
			} catch (Exception e) {
				eof = true;
				return null;
			}
		}
		return st.nextToken();
	}

	String nextString() {
		try {
			return br.readLine();
		} catch (IOException e) {
			eof = true;
			return null;
		}
	}

	int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

	long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}

	double nextDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}
}