问题 G: foreverlasting and fried-chicken

As we all know, There are two ACM heros known as foreverlasting and fried-chicken in BIT. They are immersed in perfect love respectively. The following link tells the love story of fried-chicken.

https://www.zhihu.com/question/62332494/answer/3076483871

Pedestrian1 likes graph and mathematics. He needs your help to solve an easy problem. You are given a simple undirected graph named "fried-chicken" with $n$ nodes and $m$ edges. Please note that the graph is not necessarily connected. The nodes are labeled from $1$ to $n$.

Pedestrian1 wants to know how many "foreverlasting" graphs in the "fried-chicken" graph.

The above image defines a "foreverlasting" graph.

Please note that two "foreverlasting" graphs are considered different when there is at least one different edge between the two edge sets that make up the two "foreverlasting" graphs.

In other word, the given graph is $G(V,E)$. You need to calculate the number of subgraphs �′(�′,�′)(�′⊆�,�′⊆�)G′(V′,E′)(V′⊆V,E′⊆E) which satisfy �′={�1,�2,�3,�4,�5,�6,�7,�8},�′={(�1,�3),(�2,�3),(�3,�4),(�3,�5),(�3,�6),(�3,�7),(�4,�8),(�5,�8),(�6,�8),(�7,�8)}V′={v1,v2,v3,v4,v5,v6,v7,v8},E′={(v1,v3),(v2,v3),(v3,v4),(v3,v5),(v3,v6),(v3,v7),(v4,v8),(v5,v8),(v6,v8),(v7,v8)}

Since the answer may be very large, Pedestrian1 wants to know the answer modulo $1000000007$.

The first line of input contains the integer $T$ ($1\le T\le 10$), the number of test cases. The description of test cases follows.

The first line of each test case contains two integers, $n$ and $m$ (1≤�≤1000,�≤�(�−1)21≤n≤1000,m≤2n(n−1)) — the number of nodes and the number of edges, respectively.

Each of the next $m$ lines contains the description of an edge. Each line contains two integers ��ui and ��vi (1≤��,��≤�,��≠��1≤ui,vi≤n,ui=vi) — an edge connects node ��ui to node ��vi.

It is guaranteed that no two edges connect the same unordered pair of nodes.

Furthermore, it is guaranteed that the sum of $n$ over all test cases both do not exceed $3000$.

1
8 10
1 2
1 3
1 4
1 5
1 6
1 7
8 4
8 5
8 6
8 7

1