Bessie 拥有一系列连通的无向图 $G_1, G_2, \ldots, G_K$ ($2 \le K \le 5 \cdot 10^4$)。对于每个 $1 \le i \le K$，$G_i$ 恰好有 $N_i$ ($N_i \ge 2$) 个顶点，编号为 $1 \ldots N_i$，以及 $M_i$ ($M_i \ge N_i - 1$) 条边。每个 $G_i$ 可能包含自环，但不存在连接同一对顶点的多条边。

现在 Elsie 创建了一个新的无向图 $G$，它有 $N_1 \cdot N_2 \cdots N_K$ 个顶点，每个顶点由一个 $K$ 元组 $(j_1, j_2, \ldots, j_K)$ 标记，其中 $1 \le j_i \le N_i$。在 $G$ 中，如果对于所有 $1 \le i \le K$，顶点 $j_i$ 和 $k_i$ 在 $G_i$ 中通过一条边相连，则顶点 $(j_1, j_2, \ldots, j_K)$ 和 $(k_1, k_2, \ldots, k_K)$ 之间存在一条边。

定义 $G$ 中位于同一连通分量的两个顶点之间的距离为从一个顶点到另一个顶点的路径上的最小边数。计算 $G$ 中顶点 $(1, 1, \ldots, 1)$ 与其所在连通分量中每个顶点之间的距离之和，结果对 $10^9 + 7$ 取模。

输入格式

第一行包含 $K$，即图的数量。

每个图的描述以一行 $N_i$ 和 $M_i$ 开始，随后是 $M_i$ 条边。

为了可读性，连续的图之间用空行分隔。保证 $\sum N_i \le 10^5$ 且 $\sum M_i \le 2 \cdot 10^5$。

输出格式

顶点 $(1, 1, \ldots, 1)$ 与所有可从其到达的顶点之间的距离之和，对 $10^9 + 7$ 取模。

样例

样例输入 1

2

2 1
1 2

4 4
1 2
2 3
3 4
4 1

样例输出 1

4

说明 1

$G$ 包含 $2 \cdot 4 = 8$ 个顶点，其中 $4$ 个与顶点 $(1, 1)$ 不连通。有 $2$ 个顶点距离 $(1, 1)$ 为 $1$，有 $1$ 个顶点距离为 $2$。因此答案为 $2 \cdot 1 + 1 \cdot 2 = 4$。

样例输入 2

3

4 4
1 2
2 3
3 1
3 4

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

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

样例输出 2

706

说明 2

$G$ 包含 $4 \cdot 6 \cdot 7 = 168$ 个顶点，所有顶点都与顶点 $(1, 1, 1)$ 连通。对于每个 $i \in [1, 7]$，距离 $(1, 1, 1)$ 为 $i$ 的顶点数量由以下数组的第 $i$ 个元素给出：$[4, 23, 28, 36, 40, 24, 12]$。

子任务

• 测试点 3-4 满足 $\prod N_i \le 300$。
• 测试点 5-10 满足 $\sum N_i \le 300$。
• 测试点 11-20 满足无额外限制。