L. Leylines of Lumina
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The ancient Kingdom of Lumina consists of $$$n$$$ cities connected by $$$m$$$ bidirectional magical leylines. Each leyline possesses a base resonance, represented by an integer $$$w$$$. This resonance can be positive (harmonious), negative (dissonant), or even zero (inert).

The High Mage wishes to establish a grand unified network—a subset of exactly $$$n - 1$$$ leylines that connects all $$$n$$$ cities together so that magic can flow freely between any two cities.

The overall instability of a chosen network is defined as the product of the resonances of its constituent leylines. To prevent a catastrophic magical surge, the High Mage must select a network that minimizes this instability.

Because the leylines are powerful, the minimum instability can be an exceptionally large positive or negative number. You are tasked with finding the minimum possible instability and reporting it modulo $$$10^9 + 7$$$.

Note on Modulo Arithmetic: The answer must be the mathematically correct modulo. If the true minimum product is $$$P$$$, you should output $$$(P \pmod{10^9 + 7} + 10^9 + 7) \pmod{10^9 + 7}$$$. You are minimizing the actual integer product first, and then applying the modulo to that minimum value.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$n - 1 \le m \le 2 \cdot 10^5$$$) — the number of cities and the number of leylines, respectively.

Each of the following $$$m$$$ lines contains three integers $$$u$$$, $$$v$$$, and $$$w$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$, $$$-10^9 \le w \le 10^9$$$) — indicating a bidirectional leyline connecting city $$$u$$$ and city $$$v$$$ with a magical resonance of $$$w$$$.

It is guaranteed that for each test case, the given graph is simple (contains no self-loops and no multiple edges between the same pair of cities) and that it is always possible to connect all cities (the graph is connected).

It is also guaranteed that the sum of $$$n$$$ and the sum of $$$m$$$ over all test cases do not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print a single integer on a new line — the minimum possible product of the edge weights of a spanning tree, modulo $$$10^9 + 7$$$.

Example
Input
6
4 5
1 2 2
2 3 -3
3 4 -4
4 1 5
1 3 1
3 3
1 2 -2
2 3 5
3 1 -1
4 4
1 2 2
2 3 3
3 4 4
1 4 5
4 4
1 2 -2
2 3 -3
3 4 -4
1 4 -5
5 5
1 2 -1
2 3 -2
3 4 -3
4 5 -4
5 1 -5
3 3
1 2 1000000000
2 3 1000000000
1 3 0
Output
999999967
999999997
24
999999947
24
0
Note
  • In the first test case, the minimum possible product is $$$-40$$$ (using edges with weights $$$2$$$, $$$5$$$, and $$$-4$$$). $$$-40 \pmod{10^9 + 7}$$$ is $$$999999967$$$.
  • In the second test case, the spanning trees have products $$$-10$$$, $$$2$$$, and $$$-5$$$. The minimum is $$$-10$$$. $$$-10 \pmod{10^9 + 7}$$$ is $$$999999997$$$.
  • In the third test case, all resonances are positive. We minimize the product by picking the smallest absolute weights: $$$2$$$, $$$3$$$, and $$$4$$$. The product is $$$24$$$.
  • In the fourth test case, $$$3$$$ edges are required. Picking any $$$3$$$ negative edges yields a negative product. To minimize it (make it as negative as possible), we pick the largest absolute weights: $$$-3$$$, $$$-4$$$, and $$$-5$$$. The product is $$$-60$$$. $$$-60 \pmod{10^9 + 7}$$$ is $$$999999947$$$.
  • In the fifth test case, $$$4$$$ edges are required. The product of $$$4$$$ negative numbers is positive. To minimize a positive product, we pick the smallest absolute weights: $$$-1$$$, $$$-2$$$, $$$-3$$$, and $$$-4$$$. The product is $$$24$$$.
  • In the sixth test case, taking the edges with weights $$$10^9$$$ and $$$0$$$ yields a product of $$$0$$$. Since no negative product can be formed, $$$0$$$ is the minimum.