Your country consists of \(n\) cities. Each city contains exactly one simple path. You are required to solve \(q\) queries if you want to visit the cities of your country.

In each query, you are required to select two cities \(A\) and \(B\) where city \(A\) is your current location. You must stop when you reach your destination. Your task is to determine that if each city that is situated on the simple path between \(A\) and \(B\)  can be selected as the destination (both included), what is the expected value of the distance that is covered by you when you starts from city \(A\).

As the expected value can be represented as \(P \over Q\) where \(P\) and \(Q\) are co-prime to each other. You are required to determine \(PQ^{-1} \bmod (10 ^ 9 + 7)\).

Note: The distance referred here is the shortest distance between the two cities.

Input format

• First line: \(n\) denoting the number of cities in the country

• Next \(n - 1\) lines: \(u, v,\) and \(w\) three space-separated integers that denote city \(u\) and city \(v\) are directly connected to each other at a distance \(w\)

• Next line: \(q\) denoting the number of queries

• Next \(q\) lines: \(A\) and \(B\) denoting two space-separated as described in the problem statement

Output format

Print \(q\) lines containing a single integer that denotes the required answer.

Constraints

\(1 \leq n, q \leq 3 \cdot10 ^ 5\)

\(1 \leq u, v, A, B \leq n\)

\(1 \leq w \leq 10 ^ 8\)