Ailin is a beautiful girl who likes math and one day she decides to study about series in order to distract herself. She starts reading about the Lucas series and because she likes the numbers greater than two, she defines the series: 3 if n = 1 L(n) = 4 if n = 2 L(n−1)+L(n−2) ifn≥3 Ailin also likes the trees, so she has a weighted tree, and she needs to run Q queries on the tree, each of which can be one of the following two types: • 1 A B: Calculate the distance between A and B. • 2 A B: Add the first elements of the Lucas series to the edges which lie on a simple path between nodes A and B. It’s Saturday and she wants to solve the problem quickly and then go to shopping... Can you help her? Input Input contains several test cases. The first line in the each test case contains a single integer n, the number of vertices in the tree (1 ≤ n ≤ 105). The next n − 1 lines contains three integers ai, bi and ci (1 ≤ ai,bi ≤ n, 1 ≤ ci ≤ 109) describing the edges of the graph, it means a edge with ci distance between nodes ai and bi (the vertices are indexed from 1 to n). Next line contains an integer Q, the number of queries (1 ≤ Q ≤ 105). The next Q lines contains three integers T, A and B (1 ≤ A,B ≤ n, 1 ≤ T ≤ 2) describing the queries. The distance between nodes may be very large, so compute the answers modulo 109 + 7. There is at least one query of the first type. See the examples below for more details. Output For each query of type 1, output one line with the answer required. Sample Input 6 232 213 351 141 161 6 115 263 115 144 234 164
2/2 Sample Output 6 17 0 12