#include<iostream>#include<stdio.h>#include<string.h>#include<string>#include<queue>#include<cmath>#include<algorithm>#include<map>#include<vector>#include<sstream>#include<ctime>using namespace std;#define mp make_pair#define pb push_backtypedef double db;typedef long long LL;typedef unsigned long long uLL;#define rep(i,n) for(int i=0;i<n;++i)const int MAXN = 222;const int P = (int)1e9 + 7; bool v[ MAXN ];LL fac[ MAXN ];LL inv[ MAXN ];LL powmod(LL a, int b,int c){ LL r = 1; while(b){ if(b&1) r=r*a%c; a=a*a%c; b>>=1; } return r;}LL f[ MAXN ][ MAXN ], g[ MAXN ];LL gg[] = { 1, 1,2,500000008,666666682,41666693,600000069,101389053,901587724,114509997,176369600,858764043,158979654,136968886,3213595,628013761,507253219,924206947,663022036,401539795,390732166,414164991,544365989,759975812,228545897,963148560,730839818,248860851,322049024,647862652,35885315,95430693,753047960,56602915,602283702,245728180,909983212,205700029,678438757,918483018,860433461,711614819,547055075,473080234,292834990,862755700,788418399,96949630,201842182,203084656,811656242,419204035,901465170,29590107,963342504,685055701,573818368,768504,492911134,668955468,678575876,211166970,430417802,352013461,906836755,321890789,985618544,228278426,765561361,32305215,504896273,864160306,380089289,863722954,945334512,916042965,608907988,813299699,66938594,916603174,964220197,675053053,448628329,67510807,473048784,955205503,714214329,305433620,300868902,952644560,293675862,316050433,360663689,10627532,365444170,757472341,651393100,810445620,852698195,642975486,569882533,634428909,592981936,340371047,903751054,274040720,736732301,244778448,120138183,369042190,330920553,639088110,296591580,608621205,717803557,987267934,656316480,350142326,227660467,273743269,403355198,645851179,150092636,374957750,854080067,380272343,2645277,781210128,457606690,349282169,131009796,82693052,844338840,848147620,43151812,105984049,357815714,330441332,188122385,524781892,396176002,970426365,20866207,694141444,923649782,416351825,274616727,138698493,573585010,370337733,429815183,444757918,639563709,920997504,774213768,381769844,791624770,838424247,465821290,485818646,202823425,508895504,243131992,805695777,324136722,452314131,920011990,553173193,167385265,346760568,167401807,371303468,938284091,480074300,429858369,129688758,654691087,987537624,925163844,115175319,506766520,129645170,863073288,150895605,386007440,644988471,68525488,885704799,545777947,655988027,146439275,633728604,153353955,9819171,245585103,929245860,980023198,723968929,665823701,274548388,299635953,609493543,579675753,561953346,98044287,397410030,260427012,534444290,889792442,414323433,360696450,424788705,331380765,847726087,92793261,654122579,463605362,538764513,849051755,787745528,70040473,985614743};void update(LL &a, LL b){ a=(a+b)%P;}void pre(){ fac[0]=1; for(int i=1;i<MAXN;++i) fac[i] = fac[i-1]*i%P; inv[0]=1; for(int i=1;i<MAXN;++i) inv[i] = powmod( fac[i], P - 2, P ) %P; f[1][1] = 1; g[1] = 1; for(int i = 2; i < MAXN; ++ i){ g[i]=0; for(int j = 1; j < i; ++ j) { LL sum = 1, add = j; for(int sub = 0; sub <= j; ++ sub){ update(f[i][1 + sub ] ,( f[i-1][j] * sum) % P * inv[1+sub] % P ); sum = sum * add % P; -- add; } } for(int j = 1; j <= i; ++ j) update( g[i], f[i][j] ) ; }}vector< int > E[ MAXN ];int n, m ;int sz;void dfs(int x){ if(v[x]) return; v[x] = 1; ++ sz; for(int i=0;i<E[x].size();++i) dfs( E[x][i]) ;}int ind[ MAXN ];int main(){ pre(); int T; cin >> T; while(T --) { cin >> n >> m; for(int i=0;i<n;++i) E[i].clear(), v[i]=0, ind[i] = 0; for(int i=0;i<m;++i){ int a, b; scanf("%d%d", &a, &b); if(a == b) continue; E[ b ].push_back( a ) ; ++ ind[ a ]; } LL ans = 1, rem = n; for(int i = 0; i < n; ++ i) if(ind[i] == 0) { sz = 0; dfs(i); ans =(ans * g[sz])%P; } for(int i = 0; i < n; ++ i) if( ! v[i] ) { sz = 0; dfs(i); ans = ans * gg[sz] % P; } cout << ans * fac[n] % P << endl; } return 0;}
