23699번 - Inner Product 다국어

문제

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)$.

제한

힌트