Підрахунок графів

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

Нехай f_G(a, b) — це булева функція, яка повертає істину, якщо існує шлях від вершини $1$ до вершини $a$, що проходить рівно $b$ ребер, для 1 \leq a \leq n і 0 \leq b. В іншому випадку функція повертає хибність. Якщо по ребру проходять кілька разів, це враховується в кількість ребер.

Ельза хоче скопіювати Бесі. Вона прагне створити ненаправлений граф G', такий що f_{G'}(a, b) = f_G(a, b) для всіх $a$ і $b$.

Ваше завдання — порахувати кількість різних графів G', які Ельза може створити, за модулем 10^9 + 7. Як і $G$, граф G' може містити петлі, але не може мати паралельних ребер (це означає, що існує всього 2^{(n^2 + n) / 2} різних графів на $n$ вершинах).

Кожен вхід містить $t$ тестів, які повинні вирішуватися незалежно. Гарантується, що сума n^2 по всіх тестах не перевищить 10^5.

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