Teacher Mai 拥有 $m+1$ 棵树，$T_0, T_1, \dots, T_m$。$T_0$ 由一个编号为 $0$ 的顶点组成。

他通过以下方式生成 $T_i$：获取 $T_{a_i}$ 和 $T_{b_i}$ 的副本。在 $T_{a_i}$ 中编号为 $c_i$ 的顶点与 $T_{b_i}$ 中编号为 $d_i$ 的顶点之间添加一条长度为 $l_i$ 的边。对新树中的顶点重新编号。设 $k$ 为 $T_{a_i}$ 中的顶点数。他保持 $T_{a_i}$ 中顶点的标签不变，并将 $T_{b_i}$ 中顶点的标签加上 $k$。

如果有一棵包含 $n$ 个顶点 $v_0, v_1, v_2, \dots, v_{n-1}$ 的树 $T$，则 $F(T) = \sum_{i=0}^{n-1} \sum_{j=i+1}^{n-1} d(v_i, v_j)$（其中 $d(v_i, v_j)$ 表示 $v_i$ 和 $v_j$ 之间的距离）。

对于每个 $i$ ($1 \le i \le m$)，他想知道 $F(T_i)$ 的值。

输入格式

第一行包含一个整数 $T$ —— 测试用例的数量 ($1 \le T \le 100$)。

对于每个测试用例，第一行包含一个整数 $m$ ($1 \le m \le 60$)，随后有 $m$ 行。第 $i$ 行包含五个数字 $a_i, b_i, c_i, d_i, l_i$ ($0 \le a_i, b_i < i, 0 \le l_i \le 10^9$)。保证 $T_{a_i}$ 中存在编号为 $c_i$ 的顶点，且 $T_{b_i}$ 中存在编号为 $d_i$ 的顶点。

输出格式

对于每个测试用例，在第 $i$ 行输出 $F(T_i)$ 对 $10^9 + 7$ 取模的结果。

样例

输入 1

1
3
0 0 0 0 2
1 1 0 0 4
2 2 1 0 3

输出 1

2
28
216