Masha has a connected undirected graph
G with
N vertices labeled with
1…N and
M edges (
\(1 \leq N \leq10^2\),
\(N-1 \leq M \leq \frac {N^2 +N}{2}\)).
G can contain loops (edges from a vertex to a vertex), but does not have parallel edges (multiple edges connecting the same endpoints).
Let
\(f_G(a,b)\) be a boolean function that evaluates to true if there is a path from node
1 to node
a that traverses exactly
b edges, for
\(1 \leq a \leq N\) and
\(0 \leq b\), and false otherwise. If the edge is traversed multiple times, this number is included in the answer.
Dasha wants to repeat after Masha. In particular, she wants to construct an undirected graph
G′ such that
\(f_{G'}(a,b)=f_G(a,b)\ ) for all
a and
b.
Count the number of different
G′ graphs Dasha can create modulo
\(10^9+7\). Like
G,
G′ can contain loops but cannot have parallel edges (meaning there are only
\(2^ { \frac {N^2+N} {2}}\) different graphs on
N vertices).
Each input contains
T (
\(1 \leq T \leq \frac {10^5}{4}\)) tests that must be decided independently. It is guaranteed that the sum of
\(N^2\) over all tests will not exceed
\(10^5\).
Input
The first input line contains
T, the number of tests.
The first line of each test contains two integers
N and
M.
The next
M lines of each test contain two integers
x and
y (
\(1 \leq x \leq y \leq N\)) denoting the edge between
x and
y in
G.
The tests are separated by a blank line for readability.
Imprint
For each test, print the number of different
G′ modulo
\(10^9+7\) on a separate line.
Examples
| # |
Input |
Output |
Note |
| 1 |
1
5 4
1 2
23
14
3 5
| 3 |
G′ can be equal to G′ or one of the following two columns:
5 4
1 2
14
34
3 5
5 5
1 2
23
14
34
3 5
|
| 2 |
7
46
1 2
23
34
1 3
24
14
5 5
1 2
23
34
4 5
15
5 7
1 2
1 3
15
24
3 3
34
4 5
66
1 2
23
34
4 5
5 6
66
67
1 2
23
1 3
14
4 5
5 6
16
10 10
1 1
1 2
1 3
14
15
16
17
18
19
1 10
22 28
1 2
23
34
4 5
5 6
67
17
18
39
8 10
10 11
10 12
10 13
10 14
11 15
12 16
13 17
14 18
9 15
9 16
9 17
9 18
15 19
19 20
15 20
16 21
21 22
16 22
| 45
35
11
1
15
371842544
256838540 |
This is an example of a larger test.
Be sure to display the answer modulo \(10^9+7\).
Note that the answer for the penultimate test is \(2^{45}\ \ (mod\ 10^9 + 7)\). |