F. Four K3
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given an undirected graph $$$G=(V, E)$$$ with $$$n$$$ vertices and $$$m$$$ edges. Note that the graph has no multiple edges or self-loops.

A graph $$$H=(V', E')$$$ is a subgraph of G if and only if $$$V'\subseteq V$$$ and $$$E'\subseteq E$$$.

A graph $$$G'$$$ is good if and only if $$$G'$$$ is isomorphic to the graph below:

Count the good subgraph in $$$G$$$, modulo $$$10^9+7$$$.

Input

The first line contains a single integer $$$T(1\le T \le 10^5)$$$, denoting the number of test cases.

For each test case, the first line contains two integers $$$n, m$$$($$$1\le n\le 10^5, 0\le m \le 10^5$$$), denoting the number of vertices and edges of the graph.

The next $$$m$$$ lines contains two positive integer $$$u_i, v_i$$$($$$1\le u_i, v_i\le n,u_i\neq v_i$$$), denoting an edge.

It is guaranteed that $$$\sum n, \sum m \le 10^5$$$.

Output

For each test cases, output a line with a single integer, the answer moduling $$$10^9+7$$$.

Example
Input
2
6 9
1 2
2 3
1 3
5 1
5 2
1 6
6 3
4 2
3 4
3 3
1 2
1 3
2 3
Output
1
0