Bessie có một tập các đồ thị vô hướng liên thông \(G_1,G_2,\ldots,G_K\) (\(2\le K\le 5\cdot10^4\)). Với mỗi \(1\le i\le K\), đồ thị \(G_i\) có đúng \(N_i\) đỉnh (\(N_i\ge2\)), được đánh số \(1\ldots N_i\), và \(M_i\) cạnh (\(M_i\ge N_i-1\)). Mỗi \(G_i\) có thể chứa khuyên, nhưng không có nhiều cạnh nối cùng một cặp đỉnh.

Elsie tạo một đồ thị vô hướng mới \(G\) có \(N_1\cdot N_2\cdots N_K\) đỉnh. Mỗi đỉnh được gắn nhãn bởi một bộ \(K\) phần tử \((j_1,j_2,\ldots,j_K)\), trong đó \(1\le j_i\le N_i\). Trong \(G\), hai đỉnh \((j_1,j_2,\ldots,j_K)\) và \((k_1,k_2,\ldots,k_K)\) được nối bởi một cạnh khi, với mọi \(1\le i\le K\), hai đỉnh \(j_i\) và \(k_i\) được nối bởi một cạnh trong \(G_i\).

Khoảng cách giữa hai đỉnh thuộc cùng một thành phần liên thông của \(G\) là số cạnh ít nhất trên một đường đi giữa chúng. Hãy tính tổng khoảng cách từ đỉnh \((1,1,\ldots,1)\) đến mọi đỉnh nằm cùng thành phần liên thông với nó trong \(G\), lấy modulo \(10^9+7\).

Dữ liệu vào

Dòng đầu tiên chứa \(K\), số lượng đồ thị.

Mô tả mỗi đồ thị bắt đầu bằng \(N_i\) và \(M_i\) trên một dòng, tiếp theo là \(M_i\) cạnh. Các đồ thị liên tiếp được ngăn cách bằng dòng trống cho dễ đọc. Bảo đảm \(\sum N_i\le10^5\) và \(\sum M_i\le2\cdot10^5\).

Dữ liệu ra

In tổng khoảng cách từ đỉnh \((1,1,\ldots,1)\) đến mọi đỉnh có thể đi tới từ nó, lấy modulo \(10^9+7\).

Phân nhóm

• Các test 3-4 thỏa mãn \(\prod N_i\le300\).
• Các test 5-10 thỏa mãn \(\sum N_i\le300\).
• Các test 11-20 không có ràng buộc bổ sung.

Ví dụ

2

2 1
1 2

4 4
1 2
2 3
3 4
4 1

4

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

706

Nguồn

USACO 2021 January Contest, Platinum - Sum of Distances: https://usaco.org/index.php?page=viewproblem2&cpid=1092

Tác giả: Benjamin Qi.