모든 것을 뒤집기

논로니아 정부는 철도 체계의 비효율 때문에 걱정이 많다. 모든 도시 쌍은 철도 한 개로 연결되어 있지만, 예산 문제로 일부 철도는 비활성 상태이다.

이상적인 철도 구성이란, 모든 도시 쌍에 대해 활성 철도만 이용해서 두 도시를 잇는 경로가 정확히 하나 존재하는 구성이다.

당신은 논로니아어를 못 하고 철도의 활성 상태를 직접 바꿀 수도 없다. 철도를 켜거나 끌 수 있는 것은 각 도시의 리더뿐이며, 리더들은 모두 논로니아어만 한다. 정부는 당신에게 철도 체계를 이상적인 구성으로 바꾸라고 고용했다.

논로니아어를 할 줄 아는 친구가 문구 하나를 알려 주었다. lupDujHomwIj luteb gharghmey이다. 이 문구를 도시의 리더에게 말하면, 그 도시에 연결된 모든 철도의 상태가 뒤집힌다. 비활성이던 철도는 활성이 되고, 활성이던 철도는 비활성이 된다.

그림 3: 도시 1과 2에 lupDujHomwIj luteb gharghmey 문구를 적용한 결과

문구는 리더 여러 명에게 각각 한 번씩 말할 수 있다. 리더 집합을 골라 그 리더들에게만 한 번씩 연락했을 때 이상적인 구성이 되면, 그 집합을 좋은 집합이라고 한다. 좋은 집합의 개수를 세라. 두 집합은 한쪽에만 속한 리더가 하나라도 있으면 서로 다르다.

답은 $10^9 + 7$로 나눈 나머지로 출력한다.

첫 줄에 도시의 수 $N$과 처음에 활성 상태인 철도의 수 $M$이 주어진다 ($1 \le N \le 100$, $0 \le M \le \frac{N \times (N-1)}{2}$).

이어서 $M$개의 줄에 정수 $u$, $v$가 주어진다 ($1 \le u < v \le N$). 이는 처음에 활성 상태인 철도가 도시 $u$와 $v$를 잇는다는 뜻이다. 같은 도시 쌍이 두 번 나오지 않는다.

주어진 초기 구성에 대해 좋은 집합의 개수를 $10^9 + 7$로 나눈 나머지를 한 줄에 출력한다.