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:

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 $10^{9} + 7$.

Input

In the first line of input an integer $*n*$ ($1 ≤ *n* ≤ 10^{5}$), number of vertices of the tree is given.

In each of the next $*n* - 1$ lines three space-separated integers $*a*_{*i*}, *b*_{*i*}, *c*_{*i*}$ ($1 ≤ *a*_{*i*}, *b*_{*i*} ≤ *n*$, $1 ≤ *c*_{*i*} ≤ 10^{9}$) are given indicating an edge between $*a*_{*i*}$ and $*b*_{*i*}$ with weight equal to $*c*_{*i*}$.

In the next line an integer $*q*$ ($1 ≤ *q* ≤ 10^{5}$), number of vertex pairs, is given.

In each of the next $*q*$ lines two space-separated integers $*u*_{*i*}, *v*_{*i*}$ ($1 ≤ *u*_{*i*}, *v*_{*i*} ≤ *n*$) are given meaning that you must calculate $*f*(*u*_{*i*}, *v*_{*i*})$.

It is guaranteed that the given edges form a tree.

Output

Output $*q*$ lines. In the $*i*$-th line print the value of $*f*(*u*_{*i*}, *v*_{*i*})$ modulo $10^{9} + 7$.