У Бесі є зв'язний ненаправлений граф \(G\) з \(N\) вершинами, поміченими \(1\ldots N\) і \(M\) ребрами (\(1\le N\le 10^2, N-1\le M\le \frac{N^2+N}{2}\)). \(G\) може містити петлі (ребра з вершини в неї ж), але не має паралельних ребер (кілька ребер, що з'єднують одні й самі кінцеві точки).

Нехай \(f_G(a,b)\) це булева функція, яка відповідає істині, якщо існує шлях від вершини \(1\) до вершини \(a\), який проходить рівно \(b\) ребер, для \(1\le a\le N\) і \(0\le b\), і хибна інакше.

Якщо по ребру проходимо багато разів, це число включається у відповідь.

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

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

Кожне введення містить \(T\) (\(1\le T\le \frac{10^5}{4}\)) тестів, які мають вирішуватися незалежно. Гарантується, що сума \(N^2\) по всіх тестах не перевищить \(10^5\).

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

Перший рядок введення містить \(T\) кількість тестів.

Перший рядок кожного тесту містить два цілих числа \(N\) та \(M\).

Наступні \(M\) рядків кожного тесту містять два цілих числа \(x\) і \(y\) (\(1\le x\le y\le N\)), що позначають ребро між \(x\) і \(y\) \(G\).

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

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

Для кожного тесту виведіть кількість різних \(G'\) по модулю \(10^9+7\) у новому рядку.

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

1

5 4
1 2
2 3
1 4
3 5

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

3

У першому тесті, \(G'\) може дорівнювати \(G\) або одному з двох наступних графів:

5 4
1 2
1 4
3 4
3 5

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

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

7

4 6
1 2
2 3
3 4
1 3
2 4
1 4

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

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

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

6 7
1 2
2 3
1 3
1 4
4 5
5 6
1 6

10 10
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10

22 28
1 2
2 3
3 4
4 5
5 6
6 7
1 7
1 8
3 9
8 10
10 11
10 12
10 13
10 14
11 15
12 16
13 17
14 18
9 15
9 16
9 17
9 18
15 19
19 20
15 20
16 21
21 22
16 22

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

45
35
11
1
15
371842544
256838540

Не забудьте вводити відповідь за модулем \(10^9+7\). Зауважимо, що відповідь для тестів від 2 до останньої дорівнює \(2^{45}\pmod{10^9+7}\).

ОЦІНЮВАННЯ:

• У всіх тестах введення 3 \(N\le 5\).
• У всіх тестах вводів 4-5 \(M=N-1\).
• У всіх тестах вводів 6-11, якщо це не випадок коли \(f_G(x,b)=f_G(y,b)\) для всіх \(b\), тоді існує таке \(b\) \(f_G(x,b)\) істина, а \(f_G(y,b)\) брехня.
• У всіх тестах вводів 12-20 немає додаткових обмежень.