#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

const int mod = 1e9 + 7;

LL triangles(int n, vector<PII> edges)
{
	vector<VI> g(n);
	int m = SZ(edges);
	VI deg(n, 0);
	FOR (i, 0, m)
	{
		auto [u, v] = edges[i];
		deg[u]++;
		deg[v]++;
	}
	FOR (i, 0, m)
	{
		auto [u, v] = edges[i];
		if (MP(deg[u], u) < MP(deg[v], v))
			g[u].PB(v);
		else
			g[v].PB(u);
	}
	LL cnt3 = 0;
	VI used(n, 0);
	FOR (v, 0, n)
	{
		for (auto u : g[v])
			used[u] = 1;
		for (auto u : g[v])
		{
			for (auto w : g[u])
				if (used[w])
					cnt3++;
		}
		for (auto u : g[v])
			used[u] = 0;
	}
	return cnt3;
}


LL rect(int n, vector<PII> edges)
{
	vector<VI> g(n);
	int m = SZ(edges);
	FOR (i, 0, m)
	{
		auto [u, v] = edges[i];
		g[u].PB(v);
		g[v].PB(u);
	}
	LL cnt4 = 0;
	vector<LL> L(n);
	FOR (v, 0, n)
	{
		for (auto u : g[v])
			if (MP(SZ(g[u]), u) < MP(SZ(g[v]), v))
				for (auto y : g[u])
					if (MP(SZ(g[y]), y) < MP(SZ(g[v]), v))
						cnt4 += L[y], L[y]++;
		for (auto u : g[v])
			if (MP(SZ(g[u]), u) < MP(SZ(g[v]), v))
				for (auto y : g[u])
					L[y] = 0;
	}
	return cnt4;
}

void solve()
{
	int n, m;
	cin >> n >> m;
	vector<PII> e(m);
	VI d(n);
	FOR (i, 0, m)
	{
		cin >> e[i].F >> e[i].S;
		e[i].F--;
		e[i].S--;
		d[e[i].F]++;
		d[e[i].S]++;
	}
	LL c3 = triangles(n, e);
	LL c4 = rect(n, e);
	LL ans = LL(m) * (n + m - 3);
	
	
	FOR (i, 0, n)
		ans += d[i] * LL(d[i] - 1) / 2;
	cout << (ans + c3 * 3 + c4) % mod << '\n';
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int t;
	cin >> t;
	while (t--)
	{
		solve();
	}
	
	return 0;
}