Tổng Khoảng Cách

Cho $K$ đồ thị vô hướng liên thông. Đồ thị thứ $i$ có $N_i$ đỉnh và $M_i$ cạnh.

Tạo một đồ thị tích $G$ với $N_1·N_2\cdots N_K$ đỉnh, mỗi đỉnh là một bộ $K$-phần tử $(j_1,j_2,\dots ,j_K)$. Hai đỉnh $(j_1,\dots ,j_K)$ và $(j_1^{\prime },\dots ,j_K^{\prime })$ được nối bằng cạnh trong $G$ khi và chỉ khi tồn tại cạnh $(j_g,j_g^{\prime })$ trong đồ thị $g$ với mọi $g=1,\dots ,K$.

Tính tổng khoảng cách từ đỉnh $(1,1,\dots ,1)$ đến tất cả các đỉnh có thể đến được trong $G$, theo modulo ${10}^9+7$.

Dữ liệu vào

Dòng đầu tiên chứa $K$.

Tiếp theo là $K$ nhóm (cách nhau bởi dòng trống), mỗi nhóm mô tả một đồ thị:

• Dòng đầu: $N_i$ và $M_i$
• $M_i$ dòng tiếp theo: mỗi dòng chứa hai số nguyên $u$, $v$ là hai đầu của một cạnh

Dữ liệu ra

Một số nguyên duy nhất: tổng khoảng cách theo modulo ${10}^9+7$.

Ràng buộc

• $2\le K\le 5·{10}^4$
• $N_i\ge 2$, $M_i\ge N_i-1$
• $\sum N_i\le {10}^5$
• $\sum M_i\le 2·{10}^5$

Ví dụ