У Беси есть коллекция связных неориентированных графов \(G_1,G_2,\ldots,G_K\)
(\(2\le K\le 5\cdot 10^4\)). Для каждого i (\(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\) может содержать циклы, но нет двух и более ребер
между парой вершин.
Сейчас Эльза создаёт новый неориентированный граф \(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\) две вершины \((j_1,j_2,\ldots,j_K)\) и \((k_1,k_2,\ldots,k_K)\)
соединены ребром, если для всех i \(1\le i\le K\), \(j_i\) и \(k_i\) соединены ребром
в \(G_i\).
Определим расстояние между двумя вершинами в \(G\) которые лежат
в одной и той же связной компоненте как минимальное количество ребер на пути из
одной вершины в другую. Вычислите сумму расстояний между вершиной \((1,1,\ldots,1)\)
и каждой вершиной в этой же компоненте в \(G\) по модулю \(10^9+7\).
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содердит
\(K\), количество графов.
Описание каждого графа начинается с \(N_i\) и \(M_i\) в одной строке, за которой
следуют \(M_i\) ребер.
Последовательные графы разделены пустыми строками для читабельности.
Гарантируется, что \(\sum N_i\le 10^5\) и \(\sum M_i\le 2\cdot 10^5\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Сумма расстояний от вершины \((1,1,\ldots,1)\) и каждой вершины достижимой от неё по модулю
\(10^9+7\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
2 1
1 2
4 4
1 2
2 3
3 4
4 1
|
4
|