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.util.Arrays;
import java.util.ArrayList;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.List;
import java.io.BufferedReader;
import java.math.BigInteger;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.IOException;
import java.util.StringTokenizer;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author Vadim Semenov
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskD solver = new TaskD();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskD {
    private static final int MODULO = 1_000_000_007;

    private List<int[]>[] graph;
    private int[] s1;
    private int[] s2;
    private int[] s1inSubTree;
    private int[] s2inSubTree;
    private int[] subTreeSize;

    // LCA
    private int[][] parent;
    private int[] level;
    private int[] distance;

    public void solve(int testNumber, InputReader in, PrintWriter out) {
        int vertices = in.nextInt();
        graph = new List[vertices];
        for (int i = 0; i < vertices; ++i) {
            graph[i] = new ArrayList<>();
        }
        for (int i = 0; i + 1 < vertices; ++i) {
            int v = in.nextInt() - 1;
            int u = in.nextInt() - 1;
            int l = in.nextInt();
            graph[v].add(new int[]{u, l});
            graph[u].add(new int[]{v, l});
        }
        s1 = new int[vertices];
        s2 = new int[vertices];
        s1inSubTree = new int[vertices];
        s2inSubTree = new int[vertices];
        subTreeSize = new int[vertices];
        prepare(0, -1);
        anotherPrepare(0, -1, s1inSubTree[0], s2inSubTree[0]);
        level = new int[vertices];
        parent = new int[vertices][18];
        for (int[] p : parent) Arrays.fill(p, -1);
        distance = new int[vertices];
        prepareLCA(0, -1, 0, 0);

        int queries = in.nextInt();
        for (int q = 0; q < queries; ++q) {
            int u = in.nextInt() - 1;
            int v = in.nextInt() - 1;
            int lca = lca(u, v);
            int dist = (distance[u] + distance[v]);
            if (dist >= MODULO) dist -= MODULO;
            dist -= 2 * distance[lca];
            while (dist < 0) dist += MODULO;
            if (v != lca) {
                long answer = s1inSubTree[v] * 2L * dist;
                answer += s2inSubTree[v];
                answer += dist * 1L * dist % MODULO * subTreeSize[v];
                answer *= 2;
                answer -= s2[u];
                answer %= MODULO;
                if (answer < 0) answer += MODULO;
                out.println(answer);
            } else {
                long answer = (s2[v] - s2inSubTree[v]) + (s1[v] - s1inSubTree[v]) * 2L * dist + dist * 1L * dist %
                        MODULO * (vertices - subTreeSize[v]);
                answer %= MODULO;
                answer = s2[u] - 2 * answer;
                answer %= MODULO;
                if (answer < 0) answer += MODULO;
                out.println(answer);
            }
        }
    }

    private int lca(int u, int v) {
        if (level[u] < level[v]) {
            int tmp = u;
            u = v;
            v = tmp;
        }
        int diff = level[u] - level[v];
        for (int i = 0; i < parent[u].length; ++i) if (((diff >> i) & 1) == 1) {
            u = parent[u][i];
        }
        if (level[v] != level[u]) throw new AssertionError(level[v] + " " + level[u]);
        if (u == v) return v;
        for (int i = parent[v].length; i >= 0; --i) if (i < parent[v].length && parent[v][i] != parent[u][i]) {
            v = parent[v][i];
            u = parent[u][i];
        }
        return parent[v][0];
    }

    private void prepareLCA(int vertex, int parent, int level, int distance) {
        this.distance[vertex] = distance;
        this.level[vertex] = level;
        this.parent[vertex][0] = parent;
        for (int i = 1; i < this.parent[vertex].length; ++i) {
            if (this.parent[vertex][i - 1] != -1) {
                this.parent[vertex][i] = this.parent[this.parent[vertex][i - 1]][i - 1];
            }
        }
        for (int[] e : graph[vertex]) if (e[0] != parent) {
            prepareLCA(e[0], vertex, level + 1, (distance + e[1]) % MODULO);
        }
    }

    private void anotherPrepare(int vertex, int parent, int s1, int s2) {
        this.s1[vertex] = s1;
        this.s2[vertex] = s2;
        for (int[] e : graph[vertex]) {
            int to = e[0];
            if (to == parent) continue;
            long l = e[1];
            anotherPrepare(to, vertex,
                    (int) ((s1 + l * (graph.length - 2 * subTreeSize[to])) % MODULO),
                    (int) ((((s2 + l * l % MODULO * (graph.length - 2 * subTreeSize[to]) +
                            2 * l * (s1 - l * subTreeSize[to] % MODULO - 2 * s1inSubTree[to]))) % MODULO + MODULO) %
                    MODULO));
        }
    }

    private void prepare(int vertex, int parent) {
        subTreeSize[vertex] = 1;
        long s1 = 0;
        long s2 = 0;
        for (int[] e : graph[vertex]) {
            int to = e[0];
            if (to == parent) continue;
            long l = e[1];
            prepare(to, vertex);
            subTreeSize[vertex] += subTreeSize[to];
            s1 += l * subTreeSize[to] + s1inSubTree[to];
            s1 %= MODULO;
            s2 += l * l % MODULO * subTreeSize[to] + s2inSubTree[to] + 2 * l * s1inSubTree[to];
            s2 %= MODULO;
        }
        s1inSubTree[vertex] = (int) s1;
        s2inSubTree[vertex] = (int) s2;
    }
}

class InputReader {
    private final BufferedReader reader;
    private StringTokenizer tokenizer;

    public InputReader(InputStream in) {
        reader = new BufferedReader(new InputStreamReader(in));
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    public String next() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(readLine());
        }
        return tokenizer.nextToken();
    }

    public String readLine() {
        String line = null;
        try {
            line = reader.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return line;
    }
}

