Rikka 拥有多年 ACM-ICPC 的参赛经验，作为 Keping 大学的一名学生，她紧跟算法发展的潮流。

在本学期的课程中，Rikka 对线图进行了深入研究。在图论的数学学科中，简单无向图 $G$ 的线图是另一个简单无向图 $L(G)$，它表示了 $G$ 中每两条边之间的邻接关系。确切地说，对于一个没有自环或重边的无向图 $G$，其线图 $L(G)$ 是一个满足以下条件的图：

• $L(G)$ 的每个顶点代表 $G$ 中的一条边；且
• $L(G)$ 的两个顶点相邻，当且仅当它们在 $G$ 中对应的边共享一个公共端点。

给定一个简单无向图 $G$，Rikka 的研究旨在计算其线图中的顶点数。现在她决定向你展示她早期研究的一些关键结果，涉及 $G$ 的线图 $L(G)$、线图的线图 $L^2(G)$（即 $L(L(G))$）等图中的顶点数，分别记为 $|V(L(G))|, |V(L^2(G))|, \dots$。

根据具有 $n$ 个顶点和 $m$ 条边的无向图的定义，我们知道：

$$|V(L(G))| = \sum_{e} 1 = m = \frac{1}{2} \sum_{u} d_1(u)$$

其中 $d_1(u)$ 表示 $G$ 中顶点 $u$ 的度数。

一旦我们知道如何计数，对于 $G$ 中的任意边 $e$，与 $e$ 共享公共端点的边的数量（即 $e$ 在 $L(G)$ 中的度数，记为 $d'_1(e)$）为：

$$|V(L^2(G))| = \frac{1}{2} \sum_{e} d'_1(e) = \frac{1}{2} \sum_{e=(u,v)} (d_1(u) - 1 + d_1(v) - 1) = \frac{1}{2} \sum_{u} d_1(u)(d_1(u) - 1)$$

类似的简单分析可以帮助我们计算 $|V(L^3(G))|$，而 Rikka 在 2018 年 JheZiang 信息学奥林匹克竞赛中发表的一项优秀成果揭示了 $L^4(G)$ 中的顶点数为：

$$|V(L^4(G))| = \frac{1}{2} \sum_{u} (2d_1^2(u) - 13d_1(u) + 21 + 4d_2(u))d_1(u)(d_1(u) - 1) - 13(d_1(u) - 1)d_2(u) + (d_1(u) - 2)d_{2,2}(u) + d_2^2(u)$$

其中 $d_2(u)$ 是 $G$ 中所有与 $u$ 相邻的顶点的度数之和，而 $d_{2,2}(u)$ 是所有与 $u$ 相邻的顶点的度数的平方和。

基于 $L^5(G) = L^4(L(G))$ 的等式，她的最新工作取得了进一步发展。她从关于 $L^4(G)$ 的结果中推导出了一个线性可计算的方法，以 $O(n+m)$ 的时间复杂度计算 $L^5(G)$ 中的顶点数。Rikka 指出，在 $|V(L^4(G))|$ 的求和形式中所需的关于顶点的数据，暗示了具有相似定义的关于边的新数据。实际上，$d_1$ 和 $d'_1$ 之间的关系是最简单的对应关系。一个更难的对应关系是 $d_2$ 和 $d'_2$ 之间的关系。幸运的是，我们可以在线性时间内计算出所有这些关于边的新数据。因此，尝试用边的求和代替顶点的求和，为 $L^5(G)$ 中的顶点数提供了一个严格的公式。

现在你必须尝试跟上时代的潮流。在本题中，对于一个无向简单图 $G$，你需要计算 $L^6(G)$ 中的顶点数，并将结果对 $(10^9 + 7)$ 取模。

输入格式

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

对于每个测试用例，第一行包含两个整数 $n$ ($1 \le n \le 10^5$) 和 $m$ ($0 \le m \le 2 \times 10^5$)，表示给定简单无向图 $G$ 的顶点数和边数。

接下来 $m$ 行，描述图的所有边。每行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le n, u \neq v$)，表示第 $u$ 个顶点和第 $v$ 个顶点之间的一条边。

输入保证每个测试用例给定的图不包含自环或重边。

输出格式

对于每个测试用例，输出一行，包含一个整数，即 $L^6(G)$ 中的顶点数除以 $(10^9 + 7)$ 的余数。

样例

样例输入 1

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

样例输出 1

396
4

Figure 1. Illustration of a graph G and its line graph L(G)