У Бесі є колекція зв'язних неорієнтованих графів \(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\).

Формат вхідних даних

Перший рядок містить \(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\).

Приклад вхідних даних

2

2 1
1 2

4 4
1 2
2 3
3 4
4 1

Приклад вихідних даних

4

\(G\) містить \(2\cdot 4=8\) вершин, \(4\) з яких не з'єднані з вершиною \((1,1)\). Є \(2\) вершини на відстані \(1\) від вершини \((1,1)\) і \(1\) вершина на відстані \(2\).

Тому відповідь \(2 \ cdot 1 + 1 \ cdot 2 = 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

\(G\) містить \(4\cdot 6\cdot 7=168\) вершин, кожна з яких з'єднана з вершиною \((1,1,1)\). Кількість вершин на відстані \(i\) від вершини \((1,1,1)\) для кожного \(i\in [1,7]\) задано \(i\)-им елементом наступного масиву: \([4,23,28,36,40,24,12]\).

ОЦІНЮВАННЯ:

• У тестах 3-4 \(\prod N_i\le 300\).
• У тестах 5-10 \(\sum N_i\le 300\).
• У тестах 11-20 немає додаткових обмежень.