홀수 차수

어떤 공화국에 $N$개의 마을($1 \le N \le 50{,}000$)이 있고, 이 마을들은 $M$개의 무방향 도로($1 \le M \le 100{,}000$)로 연결되어 있습니다. $i$번째 도로는 서로 다른 두 마을 $A_i$와 $B_i$를 잇습니다($1 \le A_i \le N$, $1 \le B_i \le N$, $A_i \ne B_i$). 같은 두 마을을 잇는 도로가 중복해서 존재하지는 않습니다. 공화국이 반드시 연결되어 있는 것은 아니며, 서로 오갈 수 없는 마을 쌍이 있을 수도 있습니다.

침략자들이 남아 있는 모든 도로를 조사하려 하므로, 마을들은 일부 도로를 폐쇄하려 합니다. 목표는 모든 마을이 남은 도로 중 홀수 개의 끝점이 되도록 만드는 것입니다.

모든 마을이 홀수 개의 남은 도로에 연결되도록 남겨 둘 수 있는 도로 부분집합이 몇 가지인지 세십시오. 이 값이 매우 클 수 있으므로 $1{,}000{,}000{,}007$로 나눈 나머지를 출력합니다. 그런 부분집합이 존재하지 않으면 개수는 $0$입니다.

예를 들어 아래 공화국을 생각해 봅시다.

1---2
 \ /
  3---4

여기서는 정확히 두 개의 부분집합이 조건을 만족합니다. 하나는 도로 1–3, 2–3, 3–4를 남기고 1–2를 폐쇄하는 것입니다. 이때 마을 1, 2, 4는 각각 도로 하나에, 마을 3은 세 개의 도로에 연결됩니다. 다른 하나는 1–2와 3–4를 남기는 것입니다. 따라서 이 공화국의 답은 $2$입니다.

• 첫째 줄: 공백으로 구분된 두 정수 $N$과 $M$.
• 둘째 줄부터 $M+1$번째 줄까지: $i+1$번째 줄에는 $i$번째 도로를 나타내는 두 정수 $A_i$와 $B_i$가 공백으로 구분되어 주어집니다.

• 정수 하나: 모든 마을이 홀수 개의 도로에 연결되도록 남겨 둘 수 있는 도로 부분집합의 개수를 $1{,}000{,}000{,}007$로 나눈 나머지. 그런 부분집합이 없으면 $0$을 출력합니다.