У Беси есть коллекция связных неориентированных графов G1, G2, ..., Gk (2 ≤ k ≤ 5 * 104). Для каждого i (1 ≤ i ≤ k), Gi имеет ровно ni (ni ≥ 2) вершин, помеченных 1..ni и mi (mi ≥ ni − 1) ребер. Каждый Gi может содержать циклы, но нет двух и более ребер между парой вершин.

Сейчас Эльза создаёт новый неориентированный граф G с n1 * n2 * ... * nk вершинами, каждая из которых помечена k-плетом (j1, j2,..., jk), где 1 ≤ ji ≤ ni. В G две вершины (j1, j2,...,jk) и (k1, k2,..., kk) соединены ребром, если для всех i (1 ≤ i ≤ k), ji и ki соединены ребром в Gi.

Определим расстояние между двумя вершинами в G которые лежат в одной и той же связной компоненте как минимальное количество ребер на пути из одной вершины в другую. Вычислите сумму расстояний между вершиной (1, 1, ..., 1) и каждой вершиной в этой же компоненте в G по модулю 109 + 7.

Входные данные

Первая строка содердит k, количество графов.

Описание каждого графа начинается с ni и mi в одной строке, за которой следуют mi ребер.

Последовательные графы разделены пустыми строками для читабельности. Гарантируется, что ∑ ni ≤ 105 и ∑ mi ≤ 2 * 105.

Выходные данные

Сумма расстояний от вершины (1, 1, ..., 1) и каждой вершины достижимой от неё по модулю 109 + 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].