Edge Coloring

An undirected graph $G$ is given. $G$ has no self loops, but it can have more than one edge between the same pair of vertices. Choose a subset of the edges of $G$. For every vertex $v$, the number of chosen edges incident to $v$ must be odd. A vertex with no chosen incident edge counts as even. Find the number of valid choices modulo $100000007$.

The first line has $n$ and $m$. $n$ is the number of vertices and $m$ is the number of edges. Each of the next $m$ lines has $u$ and $v$. The $i$th edge joins $u$ and $v$. Vertices are numbered from $1$ to $n$.

• $1 \le n \le 100$
• $0 \le m \le 800$
• Every edge satisfies $u \ne v$ and $1 \le u, v \le n$.

Print the number of valid choices modulo $100000007$.

Dashed edges are not chosen and solid edges are chosen. The figure below shows the four possible cases.