У Маши есть связный ненаправленный граф
G с
N вершинами, помеченными
1…N и
M ребрами (
\(1 \leq N \leq10^2\),
\(N-1 \leq M \leq \frac {N^2+N}{2}\)).
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^{ \frac {N^2+N} {2}}\) различных графов на
N вершинах).
Каждый ввод содержит
T (
\(1 \leq T \leq \frac {10^5}{4}\)) тестов, которые должны решаться независимо. Гарантируется, что сумма
\(N^2\) по всем тестам не превысит
\(10^5\).
Входные данные
Первая строка ввода содержит
T, количество тестов.
Первая строка каждого теста содержит два целых числа
N и
M.
Следующие
M строк каждого теста содержат два целых числа
x и
y (
\(1 \leq x \leq y \leq N\)), обозначающих ребро между
x и
y в
G.
Тесты разделены пустой строкой для читабельности.
Выходные данные
Для каждого теста выведите количество различных
G′ по модулю
\(10^9+7\) на отдельной строке.
Примеры
| № |
Входные данные |
Выходные данные |
Примечание |
| 1 |
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 |
| 2 |
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^{45}\ \ (mod\ 10^9 + 7)\). |