### 问题描述 小齐有一系列连通的无向图 $G_1, G_2, \ldots, G_K$，每个图 $G_i$ 都有 $N_i$ 个顶点（$N_i \geq 2$）和 $M_i$ 条边（$M_i \geq N_i - 1$）。每个图 $G_i$ 中可能包含自环，但不能有同一对顶点之间的多条边。 现在，小齐创建了一个新的无向图 $G$，其中有 $N_1 \cdot N_2 \cdot \ldots \cdot N_K$ 个顶点，每个顶点用 $K$-元组 $(j_1, j_2, \ldots, j_K)$ 表示，其中 $1 \leq j_i \leq N_i$。在图 $G$ 中，如果对于所有 $1 \leq i \leq K$，顶点 $(j_1, j_2, \ldots, j_K)$ 和 $(k_1, k_2, \ldots, k_K)$ 在图 $G_i$ 中都有边相连，那么它们在图 $G$ 中也有边相连。 定义图 $G$ 中属于相同连通分量的两个顶点之间的距离为沿路径从一个顶点到另一个顶点的最小边数。计算顶点 $(1, 1, \ldots, 1)$ 到与其在同一连通分量中的所有顶点的距离之和，取模 $10^9 + 7$。 ### 输入格式 第一行包含一个整数 $K$，表示图的数量。 接下来每个图的描述以 $N_i$ 和 $M_i$ 开始，分别表示图 $G_i$ 的顶点数和边数。之后的 $M_i$ 行描述图 $G_i$ 的边，每行包含两个整数 $a$ 和 $b$，表示图 $G_i$ 中的一条边连接顶点 $a$ 和 $b$。 相邻图的描述之间用一个空行隔开。 ### 输出格式 输出顶点 $(1, 1, \ldots, 1)$ 到与其在同一连通分量中的所有顶点的距离之和，取模 $10^9 + 7$。 ### 样例输入 ``` 2 2 1 1 2 4 4 1 2 2 3 3 1 3 4 ``` ### 样例输出 ``` 4 ``` ### 评测数据规模 $\sum N_i \leq 10^5$ 且 $\sum M_i \leq 2 \cdot 10^5$。