간선 색칠

무방향 그래프 $G$가 주어진다. $G$에는 자기 자신으로 이어지는 간선은 없지만 같은 두 정점을 잇는 간선이 여러 개 있을 수 있다. $G$의 간선들 가운데 일부를 선택한다. 모든 정점 $v$에 대해 $v$에 닿은 선택된 간선의 개수가 홀수이어야 한다. 선택된 간선이 하나도 없는 경우는 짝수로 본다. 조건을 만족하는 선택의 개수를 $100000007$로 나눈 나머지를 구한다.

첫째 줄에 $n$과 $m$이 주어진다. $n$은 정점의 개수이고 $m$은 간선의 개수이다. 둘째 줄부터 $m$개 줄에 걸쳐 $u$와 $v$가 주어진다. $i$번째 간선은 $u$와 $v$를 잇는다. 정점 번호는 $1$부터 $n$까지이다.

• $1 \le n \le 100$
• $0 \le m \le 800$
• 모든 간선에 대해 $u \ne v$이며 $1 \le u, v \le n$이다.

조건을 만족하는 선택의 개수를 $100000007$로 나눈 나머지를 출력한다.

선택하지 않은 간선은 점선으로, 선택한 간선은 실선으로 그렸다. 아래 그림은 가능한 네 가지 경우를 보여준다.