Xiao Y has a weighted undirected graph $G$ with $n$ nodes and $m$ edges, where nodes are numbered from $1$ to $n$. The $i$-th edge ($1 \le i \le m$) connects $u_i$ and $v_i$ with weight $w_i$. It is guaranteed that $G$ is connected and contains no multiple edges or self-loops.

Xiao Y foresees that time will erode the traces of graph $G$, causing some edges to become directed and others to disappear. Specifically, over time, graph $G$ will wear down into a weighted directed graph $G'$ with $n$ nodes, where for the $i$-th edge ($1 \le i \le m$) in $G$:

• There is a $\frac{1}{4}$ probability that both directed edges $u_i \to v_i$ and $v_i \to u_i$ exist, both with weight $w_i$;
• There is a $\frac{1}{4}$ probability that the directed edge $v_i \to u_i$ exists with weight $w_i$, and its reverse edge does not exist;
• There is a $\frac{1}{4}$ probability that the directed edge $u_i \to v_i$ exists with weight $w_i$, and its reverse edge does not exist;
• There is a $\frac{1}{4}$ probability that no edge exists between $u_i$ and $v_i$.

All $m$ random events are independent.

Xiao Y considers the core of an undirected graph to be its Minimum Spanning Tree (MST), and the core of a directed graph to be its Minimum Out-Branching. A subset of edges $E$ of a graph $G'$ is called an out-branching if and only if $|E| = n - 1$ and there exists a node $x$ that can reach all other nodes in $G'$ using only the directed edges in $E$. The minimum out-branching of $G'$ is the out-branching with the minimum total edge weight.

Xiao Y hopes that the core of the graph remains unchanged after the erosion of time. He wants to know the probability that the minimum out-branching of $G'$ exists and its total edge weight is equal to the total edge weight of the MST of $G$.

You need to output the answer modulo $(10^9 + 7)$. It can be proven that the answer is a rational number $\frac{a}{b}$, where $a$ and $b$ are coprime and $b$ is not a multiple of $(10^9 + 7)$. Therefore, the number $x$ you output must satisfy $0 \le x < 10^9 + 7$ and $a \equiv bx \pmod{10^9 + 7}$. It can be proven that such an $x$ is unique.

Input

The first line contains two integers $c$ and $T$, representing the test point ID and the number of test cases, respectively. The following lines contain the test cases.

For each test case, the first line contains two integers $n$ and $m$, representing the number of nodes and edges in graph $G$. The next $m$ lines each contain three integers $u_i, v_i, w_i$, describing an edge in $G$.

Output

For each test case, output a single integer representing the probability that the minimum out-branching of $G'$ exists and its total edge weight is equal to the total edge weight of the MST of $G$, modulo $(10^9 + 7)$.

Examples

Input 1

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

Output 1

750000006
171875002

Note

The sample input contains 2 test cases.

• For the first test case, since there is only one edge in the graph, as long as an edge exists in $G'$, the total weight of the minimum out-branching of $G'$ will definitely be equal to the total weight of the MST of $G$. The probability that an edge exists in $G'$ is $\frac{3}{4}$, so the answer is $\frac{3}{4}$, which is $750000006$ modulo $10^9 + 7$.
• For the second test case, among all $2^{2m} = 64$ possible configurations of $G'$, there are 13 cases where the condition is not met. Since all cases are equally likely, the answer is $1 - \frac{13}{64} = \frac{51}{64}$, which is $171875002$ modulo $10^9 + 7$.

Subtasks

For all test points: $1 \le T \le 5$ $2 \le n \le 15$, $n - 1 \le m \le \frac{n(n-1)}{2}$ $\forall 1 \le i \le m, 1 \le u_i < v_i \le n, 1 \le w_i \le m$ $\forall 1 \le i < j \le m, (u_i, v_i) \neq (u_j, v_j)$, i.e., $G$ has no multiple edges * $G$ is guaranteed to be connected.

Special Property A: $m \le 6$, $\forall 1 \le i \le m, w_i \le 2$. Special Property B: $\forall 1 \le i < j \le m, w_i = w_j$. Special Property C: $\forall 1 \le i \le m, w_i = 1$.