У Беси есть связный ненаправленный граф G с n вершинами, помеченными 1..n и m ребрами. G может содержать петли (ребра из вершины в неё же), но не имеет параллельных ребер (несколько ребер, соединяющих одни и те же конечные точки).

Пусть fG(a, b) это булевская функция, которая отвечает истина, если существует путь от вершины 1 до вершины a, который проходит ровно b ребер, для 1 ≤ a ≤ n и 0 ≤ b, и ложь иначе. Если по ребру проходим множество раз, это число включается в ответ.

Эльза хочет копировать Беси. В частности, она хочет сконструировать ненаправленный граф G′ такой, что fG′(a, b) = fG(a, b) для всех a и b.

Ваша задача посчитать количество различных графов G′, которые Эльза может создать, по модулю 109 + 7. Как и G, G′ может содержать петли но не может иметь параллельные ребра (это означает, что имеется всего 2 ^ ((n2 + n) / 2) различных графов на n вершинах).

Каждый вход содержит t тестов, которые должны решаться независимо. Гарантируется, что сумма n2 по всем тестам не превысит 105.

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

Первая строка ввода содержит количество тестов t (1 ≤ t ≤ 105 / 4).

Первая строка каждого теста содержит два целых числа n и m (1 ≤ n ≤ 102, n − 1 ≤ m ≤ (n2 + n) / 2.

Следующие m строк каждого теста содержат два целых числа x и y (1 ≤ x ≤ y ≤ n), обозначающих ребро между x и y в G.

Последовательные тесты разделены пустой строй для читабельности.

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

Для каждого теста выведите количество различных G′ по модулю 109 + 7 в новой строке.

Пример

В этом тесте G′ может быть равен G или одному из двух следующих графов:

5 4
1 2
1 4
3 4
3 5
5 5
1 2
2 3
1 4
3 4
3 5