시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 (추가 시간 없음) 256 MB111100.000%

문제

Chiaki has two trees and each tree has $n$ vertices, labeled by $1, 2, \ldots, n$. Consider the following two arrays $A = [d_1(1, 1), d_1(1, 2), \ldots, d_1(1, n), d_1(2, 1), d_1(2, 2), \ldots, d_1(2, n), \ldots, d_1(n, 1), d_1(n, 2), \ldots, d_1(n, n)]$, $B = [d_2(1, 1), d_2(1, 2), \ldots, d_2(1, n), d_2(2, 1), d_2(2, 2), \ldots, d_2(2, n), \ldots, d_2(n, 1), d_2(n, 2), \ldots, d_2(n, n)]$, where $d_1(i, j)$ is the distance between $i$ and $j$ on the first tree, and $d_2(i, j)$ is the distance between $i$ and $j$ on the second tree.

Chiaki would like to know the inner product of $A$ and $B$. By the way, the inner product of two arrays $a = [a_1, a_2, \ldots, a_m]$ and $b = [b_1, b_2, \ldots, b_m]$ is defined as $\sum_{k = 1}^{m}{a_k b_k}$.

입력

There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:

The first line contains an integer $n$ ($1 \le n \le 10^5$) --- the number of vertices in each tree.

Each of the next $(n - 1)$ lines contains three integers $u_i$, $v_i$ and $w_i$ ($1 \le u_i, v_i \le n$, $1 \le w_i \le 10^9$) --- an edge of length $w_i$ between vertices $u_i$ and $v_i$ on the first tree.

Each of the next $(n - 1)$ lines contains three integers $u_i$, $v_i$ and $w_i$ ($1 \le u_i, v_i \le n$, $1 \le w_i \le 10^9$) --- an edge of length $w_i$ between vertices $u_i$ and $v_i$ on the second tree.

It is guaranteed that the sum of $n$ in all test cases will not exceed $10^5$.

출력

For each test case, output an integer in a single line, denoting the inner product of $A$ and $B$ modulo $(10^9 + 7)$.

예제 입력 1

1
2
1 2 3
1 2 4

예제 출력 1

24