I. Black and White Coloring
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

LittleV and Little$$$\Lambda$$$ are playing an interesting graph theory game – black and white coloring!

The game happens on a simple graph of $$$n$$$ vertices and $$$m$$$ edges. As the game starts, LittleV operates first, and he can choose any number (including zero) of vertices and color any one of these vertices black or white arbitrarily. But his operation must satisfy that none of the edges connecting to two colored vertices with the same color. After that, Little$$$\Lambda$$$ needs to color the remaining vertices, while or black arbitrarily. After all the vertices are colored, the game ends.

At last, two counts the score of the graph, which is defined as the number of edges connecting two vertices with different colors. LittleV wants to minimize the score, while Little$$$\Lambda$$$ wants to maximize it. Now LittleV wonders, how many solutions are there of his operation, that could make the score do not exceed $$$\frac{m}{2}$$$? Since the number could be larger, you only need to output it modulo $$$10^9+7$$$.Two operations are different if and only if there exists a vertex that is only colored in one operation, or a vertex is colored with different colors between two operations.

Aside, two do not like dense graphs, so it is guaranteed that the degree of any vertex would not exceed $$$3$$$.

Input

The first line of input contains an integer $$$T$$$ ($$$1 \le T \le 10^6$$$), denoting the number of testcases.

For each testcase,

The first line contains two integers $$$n$$$, $$$m$$$ ($$$1 \le n, m \le 10^5$$$), denoting the number of vertices and edges.

The $$$i$$$-th line of following $$$m$$$ lines contains two integers $$$x_i$$$, $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$, $$$x_i \neq y_i$$$), denoting that the $$$i$$$-th edge is connecting $$$x_i$$$ and $$$y_i$$$. It is guaranteed that there are no multiple edges in the graph and the degree of any vertex would not exceed $$$3$$$.

It is guaranteed that the sums of $$$n$$$ and $$$m$$$ of all testcases do not exceed $$$10^6$$$.

Output

For each testcase, output a integer, denoting the number of LittleV's operations modulo $$$10^9+7$$$.

Example
Input
2
3 3
1 2
2 3
3 1
4 4
1 2
2 3
3 4
4 1
Output
0
4