Everlasting -One-

Everlasting -One-은 올해 출시된 온라인 게임이다. 조작할 수 있는 캐릭터가 많아서 빠르게 인기를 얻었다.

캐릭터는 속성으로 결정된다. 이 게임에는 $1$번부터 $N$번까지 번호가 붙은 속성이 $N$개 있고, 각 속성의 상태는 빛과 어둠 중 하나다. 따라서 캐릭터는 모두 $2^N$가지다.

캐릭터를 바꾸는 방법은 전직뿐이며, 전직은 원하는 만큼 여러 번 할 수 있다.

캐릭터 $A$에서 캐릭터 $B$로 전직할 수 있는 조건은 다음 네 조건을 모두 만족하는 속성 $a$와 $b$가 존재하는 것이다.

• 캐릭터 $A$에서 속성 $a$의 상태가 빛이다.
• 캐릭터 $B$에서 속성 $b$의 상태가 빛이다.
• $A$와 $B$에서 동시에 빛인 속성 $c$는 존재하지 않는다.
• 순서쌍 $(a, b)$가 호환된다.

순서쌍 $(a, b)$가 호환된다는 말은 다음 세 조건을 만족하는 속성 수열 $c_1, c_2, \ldots, c_n$이 존재한다는 뜻이다.

• $c_1 = a$이다.
• $c_n = b$이다.
• 모든 $i = 1, 2, \ldots, n-1$에 대해 $(c_i, c_{i+1})$ 또는 $(c_{i+1}, c_i)$가 특별한 순서쌍이다.

특별한 순서쌍의 목록은 입력으로 주어진다.

전직을 아무리 반복해도 캐릭터 $A$를 캐릭터 $B$로 바꿀 수 없으면 두 캐릭터는 본질적으로 다르다고 한다. 전직으로 서로 바꿀 수 있는 캐릭터를 같은 그룹으로 묶을 때, $2^N$가지 캐릭터가 몇 개의 그룹으로 나뉘는지 구하라. 답이 매우 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 출력한다.

입력은 여러 개의 데이터 세트로 이루어진다. 데이터 세트는 최대 $50$개이고, 입력 전체의 크기는 5 MB 미만이다.

각 데이터 세트의 형식은 다음과 같다.

N M
a1 b1
:
aM bM

각 데이터 세트의 첫 줄에는 두 정수 $N$과 $M$이 주어진다 ($1 \le N \le 10^5$, $0 \le M \le 10^5$). 이어지는 $M$개의 줄 중 $i$번째 줄에는 $i$번째 특별한 순서쌍을 나타내는 두 정수 $a_i$와 $b_i$가 주어진다 ($1 \le a_i < b_i \le N$). 같은 순서쌍이 두 번 주어지는 경우는 없다. 즉 $i \ne j$이면 $(a_i, b_i) \ne (a_j, b_j)$이다.

입력의 마지막 줄에는 $0$이 두 개 주어진다. 이 줄은 데이터 세트가 아니다.

각 데이터 세트마다 본질적으로 다른 캐릭터의 개수를 $10^9 + 7$로 나눈 나머지를 한 줄에 출력한다.