LittleV 和 LittleΛ 正在玩一个有趣的图论游戏——黑白染色！

游戏在一个包含 $n$ 个顶点和 $m$ 条边的简单图上进行。游戏开始时，LittleV 先手，他可以选择任意数量（包括零个）的顶点，并将其中任意一个顶点涂成黑色或白色。但他的操作必须满足：不存在任何一条边连接两个颜色相同的已染色顶点。此后，LittleΛ 需要将剩余的顶点任意涂成黑色或白色。当所有顶点都被染色后，游戏结束。

最后，两人计算图的得分，得分定义为连接两个颜色不同顶点的边的数量。LittleV 希望最小化得分，而 LittleΛ 希望最大化得分。现在 LittleV 想知道，有多少种他的操作方案，使得最终得分不超过 $\frac{m}{2}$？由于结果可能很大，你只需要输出其对 $10^9 + 7$ 取模的结果。如果存在一个顶点在两种操作中仅被其中一种染色，或者一个顶点在两种操作中被染成了不同的颜色，则认为这两种操作是不同的。

此外，两人不喜欢稠密图，因此保证图中任意顶点的度数不超过 $3$。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^6$)，表示测试用例的数量。

对于每个测试用例： 第一行包含两个整数 $n, m$ ($1 \le n, m \le 10^5$)，表示顶点数和边数。 接下来的 $m$ 行中，第 $i$ 行包含两个整数 $x_i, y_i$ ($1 \le x_i, y_i \le n, x_i \neq y_i$)，表示第 $i$ 条边连接 $x_i$ 和 $y_i$。保证图中没有重边，且任意顶点的度数不超过 $3$。

保证所有测试用例的 $n$ 和 $m$ 之和不超过 $10^6$。

输出格式

对于每个测试用例，输出一个整数，表示 LittleV 的操作方案数，对 $10^9 + 7$ 取模。

样例

样例输入 1

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

样例输出 1

0
4