Counting Graphs

Bessie has a connected, undirected graph $G$ with $N$ vertices labeled $1$ to $N$ and $M$ edges. $G$ may contain self-loops (edges from a vertex back to itself), but no parallel edges (multiple edges between the same pair of endpoints).

Let $f_G(a,b)$ be a boolean function that is true if there is a path from vertex $1$ to vertex $a$ that uses exactly $b$ edges, for every $1 \le a \le N$ and $0 \le b$. Otherwise it is false. If an edge is traversed several times, it is counted once for each traversal.

Elsie wants to copy Bessie. Specifically, she wants to build an undirected graph $G'$ such that $f_{G'}(a,b) = f_G(a,b)$ for all $a$ and $b$.

Count the distinct graphs $G'$ that Elsie can build, modulo $10^9+7$. Like $G$, $G'$ may contain self-loops but no parallel edges. There are $2^{\frac{N^2+N}{2}}$ distinct graphs on $N$ labeled vertices in total.

The first line contains $T$, the number of test cases ($1 \le T \le \frac{10^5}{4}$).

Each test case starts with a line containing $N$ and $M$ ($2 \le N \le 10^2$, $N-1 \le M \le \frac{N^2+N}{2}$). The next $M$ lines each contain two integers $x$ and $y$ ($1 \le x \le y \le N$), meaning that $G$ has an edge between $x$ and $y$.

Test cases are separated by blank lines for readability. The sum of $N^2$ over all test cases does not exceed $10^5$.

For each test case, print the number of distinct $G'$ modulo $10^9+7$ on its own line.