Odd Degrees

A republic has $N$ towns ($1 \le N \le 50{,}000$) connected by $M$ undirected paths ($1 \le M \le 100{,}000$). The $i$-th path joins two distinct towns $A_i$ and $B_i$ ($1 \le A_i \le N$, $1 \le B_i \le N$, $A_i \ne B_i$); no two paths connect the same pair of towns. The republic need not be connected — some pairs of towns may be unable to reach each other.

Invaders are about to take an inventory of every remaining path, so the towns want to shut some paths down. They are after a configuration in which every town is an endpoint of an odd number of the remaining paths.

Count how many subsets of paths can be kept so that every town has an odd number of remaining paths connected to it. Because this number can be very large, output it modulo $1{,}000{,}000{,}007$. If no such subset exists, the count is $0$.

For example, consider the republic below:

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

Exactly two subsets work here. One keeps the paths 1–3, 2–3, and 3–4 (and removes 1–2): towns 1, 2, and 4 each touch one path, while town 3 touches three. The other keeps 1–2 and 3–4. The answer for this republic is therefore $2$.

• Line 1: two space-separated integers $N$ and $M$.
• Lines $2 \dots M+1$: line $i+1$ contains two space-separated integers $A_i$ and $B_i$, describing the $i$-th path.

• A single integer: the number of subsets of paths whose retention leaves every town with an odd number of connected paths, taken modulo $1{,}000{,}000{,}007$. Output $0$ if no such subset exists.