그래프 개수 세기

Bessie는 정점에 $1$부터 $N$까지 번호가 붙은 연결된 무방향 그래프 $G$를 가지고 있다. 간선은 $M$개이다. $G$에는 자기 루프(정점에서 자기 자신으로 돌아오는 간선)가 있을 수 있지만, 같은 두 정점을 잇는 중복 간선은 없다.

모든 $1 \le a \le N$과 $0 \le b$에 대해, 정점 $1$에서 정점 $a$까지 정확히 $b$개의 간선을 지나는 경로가 존재하면 참, 없으면 거짓인 불리언 함수를 $f_G(a,b)$라고 하자. 간선을 여러 번 지나면, 지날 때마다 개수에 포함한다.

Elsie는 Bessie를 따라 하려고 한다. 구체적으로, 모든 $a$와 $b$에 대해 $f_{G'}(a,b) = f_G(a,b)$를 만족하는 무방향 그래프 $G'$를 만들고자 한다.

Elsie가 만들 수 있는 서로 다른 그래프 $G'$의 개수를 $10^9+7$로 나눈 나머지를 구하라. $G$와 마찬가지로 $G'$에도 자기 루프는 있을 수 있지만 중복 간선은 없다. 번호가 붙은 정점 $N$개로 만들 수 있는 그래프는 모두 $2^{\frac{N^2+N}{2}}$개이다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다 ($1 \le T \le \frac{10^5}{4}$).

각 테스트 케이스의 첫 줄에는 정수 $N$과 $M$이 주어진다 ($2 \le N \le 10^2$, $N-1 \le M \le \frac{N^2+N}{2}$). 이어지는 $M$개의 줄에는 각각 정수 $x$와 $y$가 주어지며 ($1 \le x \le y \le N$), 이는 $G$에 $x$와 $y$를 잇는 간선이 있다는 뜻이다.

테스트 케이스는 보기 좋게 빈 줄로 구분된다. 모든 테스트 케이스에 대해 $N^2$의 합은 $10^5$를 넘지 않는다.

각 테스트 케이스마다 $G'$의 개수를 $10^9+7$로 나눈 나머지를 한 줄에 출력한다.