Сума відстаней
У Бесі є колекція зв'язних неорієнтованих графів G[1], G[2], ..., G[k] (2 ≤ k ≤ 5 * 10^4). Для кожного i (1 ≤ i ≤ k), G[i] має рівно n[i] (n[i] ≥ 2) вершин, позначених 1..n[i], і m[i] (m[i] ≥ n[i] − 1) ребер. Кожен G[i] може містити цикли, але не має двох і більше ребер між парою вершин.
Ельза створює новий неорієнтований граф G з n[1] * n[2] * ... * n[k] вершинами, кожна з яких позначена k-плетом (j[1], j[2], ..., j[k]), де 1 ≤ j[i] ≤ n[i]. У G дві вершини (j[1], j[2], ..., j[k]) і (k[1], k[2], ..., k[k]) з'єднані ребром, якщо для всіх i (1 ≤ i ≤ k), j[i] і k[i] з'єднані ребром в G[i].
Відстань між двома вершинами в G, які лежать в одній і тій же зв'язній компоненті, визначається як мінімальна кількість ребер на шляху з однієї вершини в іншу. Обчисліть суму відстаней між вершиною (1, 1, ..., 1) і кожною вершиною в цій же компоненті в G за модулем 10^9 + 7.
Вхідні дані
Перша рядок містить k, кількість графів.
Опис кожного графа починається з n[i] і m[i] в одному рядку, за яким слідують m[i] ребер.
Послідовні графи розділені порожніми рядками для читабельності. Гарантовано, що ∑ n[i] ≤ 10^5 і ∑ m[i] ≤ 2 * 10^5.
Вихідні дані
Сума відстаней від вершини (1, 1, ..., 1) до кожної вершини, досяжної від неї, за модулем 10^9 + 7.
Приклад 1
G містить 2 * 4 = 8 вершин, 4 з яких не з'єднані з вершиною (1, 1). Є 2 вершини на відстані 1 від вершини (1, 1) і 1 вершина на відстані 2. Тому відповідь 2 * 1 + 1 * 2 = 4.
Приклад 2
G містить 4 * 6 * 7 = 168 вершин, кожна з яких з'єднана з вершиною (1, 1, 1). Кількість вершин на відстані i від вершини (1, 1, 1) для кожного i ∈ [1, 7] задано i-им елементом наступного масиву: [4, 23, 28, 36, 40, 24, 12].