过了，嘿嘿

#include <bits/stdc++.h>
using namespace std;
#ifdef Fread
char buf[1 << 21], *iS, *iT;
#define gc() (iS == iT ? (iT = (iS = buf) + fread (buf, 1, 1 << 21, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
#define getchar gc
#endif
template <typenameame T>
void r1(T &x) {
	x = 0;
	char c(getchar());
	int f(1);
	for(; c < '0' || c > '9'; c = getchar()) if(c == '-') f = -1;
	for(; '0' <= c && c <= '9';c = getchar()) x = (x * 10) + (c ^ 48);
	x *= f;
}

template <typename T,typename... Args> inline void r1(T& t, Args&... args) {
    r1(t);  r1(args...);
}

#define Getmod

#ifdef Getmod
const int mod  = 1e9 + 7;
template <int mod>
struct typemod {
    int z;
    typemod(int a = 0) : z(a) {}
    inline int inc(int a,int b) const {return a += b - mod, a + ((a >> 31) & mod);}
    inline int dec(int a,int b) const {return a -= b, a + ((a >> 31) & mod);}
    inline int mul(int a,int b) const {return 1ll * a * b % mod;}
    typemod<mod> operator + (const typemod<mod> &x) const {return typemod(inc(z, x.z));}
    typemod<mod> operator - (const typemod<mod> &x) const {return typemod(dec(z, x.z));}
    typemod<mod> operator * (const typemod<mod> &x) const {return typemod(mul(z, x.z));}
    typemod<mod>& operator += (const typemod<mod> &x) {*this = *this + x; return *this;}
    typemod<mod>& operator -= (const typemod<mod> &x) {*this = *this - x; return *this;}
    typemod<mod>& operator *= (const typemod<mod> &x) {*this = *this * x; return *this;}
    int operator == (const typemod<mod> &x) const {return x.z == z;}
    int operator != (const typemod<mod> &x) const {return x.z != z;}
};
typedef typemod<mod> Tm;
#endif
const int maxn = 2e2 + 5;
const int maxm = maxn << 1;

Tm c[maxn][maxn], pw2[maxn][maxn];
Tm ksm(Tm x,int mi) {
    Tm res(1);
    while(mi) {
        if(mi & 1) res = res * x;
        mi >>= 1;
        x = x * x;
    }
    return res;
}

Tm pw[maxn * maxn];

void init() {
    c[0][0] = 1;
    int i, j;
    for(i = 0; i < maxn; ++ i) {
        c[i][0] = 1;
        for(j = 1; j < maxn; ++ j)
            c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
        for(j = 0; j < maxn; ++ j) {
            pw2[i][j] = ksm(ksm(2, i) - 1, j);
        }
    }
    for(i = 0; i < maxn * maxn; ++ i) pw[i] = ksm(2, i);
}

vector<int> vc[maxn];
int n, m;

void add(int u,int v) {
    vc[u].push_back(v);
}

Tm f[maxn][maxn][maxn], g[maxn][maxn][maxn];

int dis[maxn];

int sum[maxn];

struct pii {
    int first, second;
    pii(int a = 0,int b = 0) : first(a), second(b) {}
    int operator < (const pii &b) const {
        if(first + second != b.first + b.second) return first + second < b.first + b.second;
        else return first < b.first;
    }
    int operator == (const pii &b) const {
        return first == b.first && second == b.second;
    }
};
pii a[maxn];

#define mp pii

Tm F(int a,int x,int y) {
    Tm res(0);
    Tm vis[2] = {1, mod - 1};
    for(int i = 0; i <= x; ++ i) res += vis[i & 1] * pw2[a - i][y] * c[x][i]; 
    return res;
}



void Solve() {
    int i, j;
    r1(n, m);
    Tm ans(1);
    for(i = 0; i <= n * 2; ++ i) vc[i].clear(), dis[i] = 0x3f3f3f3f;
    for(i = 0; i <= n * 2; ++ i) for(j = 0; j <= 2 * n; ++ j)
        for(int k = 0; k <= n * 2; ++ k) f[i][j][k] = g[i][j][k] = 0;
    for(i = 1; i <= m; ++ i) {
        int u, v;
        r1(u, v);
        add(u, v + n), add(v + n, u);
        add(u + n, v), add(v, u + n);
    }

    static queue<int> q;
    while(!q.empty()) q.pop();
    q.push(1); dis[1] = 0;
    while(!q.empty()) {
        int x = q.front(); q.pop();
        for(i = 0; i < vc[x].size(); ++ i) {
            int to = vc[x][i];
            if(dis[to] > dis[x] + 1) {
                dis[to] = dis[x] + 1;
                q.push(to);
            }
        }
    }


    if(dis[1 + n] == 0x3f3f3f3f) {
        for(i = 0; i <= n; ++ i) sum[i] = 0;
        for(i = 1; i <= n; ++ i) sum[min(dis[i], dis[i + n])] ++;
        for(i = 1; i <= n; ++ i) ans = ans * pw2[sum[i - 1]][sum[i]];
        printf("%d\n", ans.z);
        return ;
    }

    for(i = 1; i <= n; ++ i) a[i] = mp(min(dis[i], dis[i + n]), max(dis[i], dis[i + n]));
    sort(a + 1, a + n + 1);
    map<pii, int> ct;
    ans = 1;
    for(i = 1; i <= n; i = j + 1) {
        j = i - 1;
        while(j < n && a[j + 1] == a[i]) ++ j;
        ct[a[i]] = j - i + 1;
        int nx = a[i].first, ny = a[i].second;
        int A = ct[mp(nx - 1, ny - 1)], B = ct[mp(nx - 1, ny + 1)], D = j - i + 1;
        Tm vis[2] = {1, mod - 1};
        if(!B) g[nx][ny][(i == 1 ? 0 : D)] = 1;
        else {
            for(int x = 0; x <= D; ++ x) {
                for(int y = 0; y <= B; ++ y)
                    g[nx][ny][x] += f[nx - 1][ny + 1][y] * c[D][x] * F(B, y, D - x);
            }
        }
        for(int x = 0; x <= D; ++ x) {
            for(int y = 0; x + y <= D; ++ y) {
                f[nx][ny][x] += c[D - y][x] * pw2[A][D - x] * g[nx][ny][y];
            }
        }
        if(j == n || a[j + 1].first != nx + 1 || a[j + 1].second != ny - 1) {
            if(nx + 1 != ny) ans *= f[nx][ny][0];
            else {
                Tm tmp(0);
                for(int x = 0; x <= D; ++ x) {
                    for(int y = 0; y <= x; ++ y)
                        tmp += vis[y & 1] * c[x][y] * f[nx][ny][x] * pw[(D - y) * (D - y + 1) / 2];                }
                ans *= tmp;
            }
        }
    }
    printf("%d\n", ans.z);
}


signed main() {
    init();
    int T;
    r1(T);
    while(T --) Solve();
	return 0;
}