Chiaki 有两棵树，每棵树都有 $n$ 个顶点，编号为 $1, 2, \dots, n$。考虑以下两个数组： $A = [d_1(1, 1), d_1(1, 2), \dots, d_1(1, n), d_1(2, 1), d_1(2, 2), \dots, d_1(2, n), \dots, d_1(n, 1), d_1(n, 2), \dots, d_1(n, n)]$, $B = [d_2(1, 1), d_2(1, 2), \dots, d_2(1, n), d_2(2, 1), d_2(2, 2), \dots, d_2(2, n), \dots, d_2(n, 1), d_2(n, 2), \dots, d_2(n, n)]$, 其中 $d_1(i, j)$ 是第一棵树中 $i$ 和 $j$ 之间的距离，$d_2(i, j)$ 是第二棵树中 $i$ 和 $j$ 之间的距离。

Chiaki 想要求出 $A$ 和 $B$ 的内积。顺便提一下，两个数组 $a = [a_1, a_2, \dots, a_m]$ 和 $b = [b_1, b_2, \dots, b_m]$ 的内积定义为 $\sum_{k=1}^{m} a_k b_k$。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示每棵树的顶点数。

接下来的 $(n - 1)$ 行，每行包含三个整数 $u_i, v_i$ 和 $w_i$ ($1 \le u_i, v_i \le n, 1 \le w_i \le 10^9$)，表示第一棵树中连接顶点 $u_i$ 和 $v_i$ 的一条长度为 $w_i$ 的边。

再接下来的 $(n - 1)$ 行，每行包含三个整数 $u_i, v_i$ 和 $w_i$ ($1 \le u_i, v_i \le n, 1 \le w_i \le 10^9$)，表示第二棵树中连接顶点 $u_i$ 和 $v_i$ 的一条长度为 $w_i$ 的边。

保证所有测试数据中 $n$ 的总和不超过 $10^5$。

输出格式

对于每组测试数据，输出一行一个整数，表示 $A$ 和 $B$ 的内积对 $(10^9 + 7)$ 取模的结果。

样例

输入 1

1
2
1 2 3
1 2 4

输出 1

24