거리의 합

벳시는 연결되어 있고 방향이 없는 그래프 $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$에는 자기 루프가 있을 수 있지만, 같은 두 정점을 잇는 다중 간선은 없습니다.

엘시는 정점이 $N_1\cdot N_2\cdots N_K$개인 새로운 무방향 그래프 $G$를 만듭니다. $G$의 각 정점은 $K$-튜플 $(j_1,j_2,\ldots,j_K)$ ($1\le j_i\le N_i$)로 표시됩니다. $G$에서 두 정점 $(j_1,j_2,\ldots,j_K)$와 $(k_1,k_2,\ldots,k_K)$는, 모든 $1\le i\le K$에 대해 $j_i$와 $k_i$가 $G_i$에서 간선으로 연결되어 있으면 간선으로 연결됩니다.

같은 연결 요소에 속한 두 정점 사이의 거리는 한 정점에서 다른 정점까지 가는 경로의 간선 수의 최솟값입니다. $(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$로 나눈 나머지로 출력합니다.