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.

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.

提交代码