Bessie 有一个连通无向图G。G有N个编号为 1…N 的结点，以及M 条边（1≤N≤$10^2$,N−1≤M≤${N^2+N \over 2}$。G 有可能包含自环（一个结点连到自身的边），但不包含重边（连接同一对结点的多条边）。令 fG(a,b) 为一个布尔函数，对于每一个 1≤a≤N 和 0≤b，如果存在一条从结点 1 到结点 a 的路径恰好经过了 b 条边，则函数值为真，否则为假。如果一条边被经过了多次，则这条边会被计算相应的次数。

Elsie 想要复制 Bessie。具体地说，她想要构造一个无向图 G′，使得对于所有的 a 和b，均有 fG′(a,b)=fG(a,b)。

你的工作是计算 Elsie 可以构造的图 G′ 的数量，对 $10^9$+7 取模。与 G 一样，G′ 可以包含自环而不能包含重边（这意味着对于 N 个有标号结点共有 2${N2+N \over 2}$ 个不同的图）。

每个输入包含 T（1≤T≤${10^5\over4}$）组独立的测试用例。保证所有测试用例中的 $N^2$ 之和不超过 $10^5$。

输入格式（从终端 / 标准输入读入）：

输入的第一行包含 T，为测试用例的数量。每个测试用例的第一行包含整数N 和M。

每个测试用例的以下 M 行每行包含两个整数x 和 y（1≤x≤y≤N），表示 G 中存在一条连接 x 与 y 的边。

为提高可读性，相邻的测试用例之间用一个空行隔开。

输出格式（输出至终端 / 标准输出）：

对每个测试用例，输出一行，为不同的 G′ 的数量，对 $10^9$+7 取模。

输入样例：

1

5 4
1 2
2 3
1 4
3 5

输出样例：

3

在第一个测试用例中，G′ 可以等于 G，或以下两个图之一：

5 4
1 2
1 4
3 4
3 5

5 5
1 2
2 3
1 4
3 4
3 5

输入样例：

7

4 6
1 2
2 3
3 4
1 3
2 4
1 4

5 5
1 2
2 3
3 4
4 5
1 5

5 7
1 2
1 3
1 5
2 4
3 3
3 4
4 5

6 6
1 2
2 3
3 4
4 5
5 6
6 6

6 7
1 2
2 3
1 3
1 4
4 5
5 6
1 6

10 10
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10

22 28
1 2
2 3
3 4
4 5
5 6
6 7
1 7
1 8
3 9
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

有一些较大的测试用例。确保你的答案对 $10^9$+7 取模。注意倒数第二个测试用例的答案为 $2^45$(mod$10^9$+7)。

测试点性质：

• 测试点 3 的所有测试用例满足N≤5。
• 测试点 4-5 的所有测试用例满足 M=N−1。
• 测试点 6-11 的所有测试用例中，如果并非对于所有的 b 均有 fG(x,b)=fG(y,b)，则存在b 使得 fG(x,b) 为真且 fG(y,b) 为假。
• 测试点 12-20 中的测试用例没有额外限制。