Підрахунок графів
У Бесі є зв'язний ненаправлений граф 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′, які Ельза може створити, за модулем 10^9 + 7. Як і G, граф G′ може містити петлі, але не може мати паралельних ребер (це означає, що існує всього 2 ^ ((n^2 + n) / 2) різних графів на n вершинах).
Кожен вхід містить t тестів, які повинні вирішуватися незалежно. Гарантується, що сума n^2 по всіх тестах не перевищить 10^5.
Вхідні дані
Перша стрічка вводу містить кількість тестів t (1 ≤ t ≤ 10^5 / 4).
Перша стрічка кожного тесту містить два цілих числа n і m (1 ≤ n ≤ 10^2, n − 1 ≤ m ≤ (n^2 + n) / 2).
Наступні m рядків кожного тесту містять два цілих числа x і y (1 ≤ x ≤ y ≤ n), що позначають ребро між x і y в G.
Послідовні тести розділені пустим рядком для зручності читання.
Вихідні дані
Для кожного тесту виведіть кількість різних G′ за модулем 10^9 + 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