Problem Description

You are given a cactus with $n$ vertices and $m$ edges. There is a 1 Ohm resistor on every edge.

Let $f(s,t)$ be the equivalent resistance between the vertex $s$ and the vertex $t$.

Print $\sum_{1\leq s<t\leq n} f(s,t)$.

Note: a cactus (sometimes called a cactus tree) is a connected graph in which any two simple cycles have at most one vertex in common. Equivalently, it is a connected graph in which every edge belongs to at most one simple cycle.

Input

The first line contains one integer $T (1\leq T\leq 7)$ - the number of the test cases.

For each test case, the first line contains two integers $n,m(1\leq n\leq 2 \times 10^5, 1\leq m\leq 4\times 10^5)$.

Each of the following $m$ lines contains three integers $u,v (1\leq u\neq v\leq n)$.

Output

For each test case, print the answer modulo $10^9+7$. That is,the answer can be represented as a fraction $a/b$ where $(a,b)=1$, output $c(0\leq c<10^9+7)$ such that $bc \equiv a \pmod {10^9+7}$.

1
4 4
1 2
1 3
2 3
1 4

333333342