飞机票： http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=34531

题意：就是给你n个人，m种关系a b，b是a的父亲，且父亲只有一个，而且自己不可能是自己的祖先，求父亲在儿子前面的方案数取模

分析：题意稍微想下其实是一堆树，我们可以先把无根转换为有根，就是把森林转换成树，我们可以把没有父亲的借点全部连在0这个节点上，这样就是一棵树。然后怎么求解呢。假设当前的节点fa，它有3个儿子，且每个儿子那一块分别有i1，i2，i3个人，而且每个的方案数分别为j1，j2，j3。。。那我们可以知道除了当前的父节点一共有i1+i2+i3个人，假设为sump，当前的父节点肯定要在他们前面，所以不用计算，位置固定，然后下面三个子树可以随机组合，就是说我们可以有C(sump,i1)种方案来放置i1中的人，但是这里还不够完整，因为这个还没有排列好，就是说i1中的人顺序应该怎么样，因为我们知道j1，所以只要两个相乘就可以，why?因为选i1的方案数就是选取了i1个位置，然后他们的方案共有j1，所以两个相乘就可以，就是C（sump,i1)*j1,那么i2就不是这样求了，因为sump减少了i1个人，所以只有sump-i1个人了所以是C（sump-i1,i2)*j2,那么第三个就是C(sump-i1-i2,i3)*j3，这样方案就是了，然后将三个相乘就是当前的方案数了。记得取模不是一般的取模，因为带有除法，但是有模版，接下来我要证明无论顺序怎么样都没有问题：C（sump,i1)*C(sump-i1,,i2)=C(sump,i2)*C(sump-i2,i1)其实很简单，左边展开和右边张开通分就可以然后啪啪啪就可以AC了~

/*
Author:Chieh
Because Of Coding
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#define INF 1e9
#define EPS 1e-9
#define LL long long
#define MOD 1000000007
using namespace std;
const int maxn=12345*4;
vector<int> V[maxn];
int n,m;
int fa[maxn];
void init()
{
    memset(fa,0,sizeof(fa));
    scanf("%d%d",&n,&m);
    V[0].clear();
    for(int i=1; i<=n; i++)
    {
        V[i].clear();
    }
    int u,v;
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d",&u,&v);
        fa[u]=v;
    }
    for(int i=1; i<=n; i++)
    {
        u=fa[i];
        V[u].push_back(i);
    }
}
LL exp_mod(LL a, LL b, LL p)
{
    LL res = 1;
    while(b != 0)
    {
        if(b&1) res = (res * a) % p;
        a = (a*a) % p;
        b >>= 1;
    }
    return res;
}

LL Comb(LL a, LL b, LL p)
{
    if(a < b)   return 0;
    if(a == b)  return 1;
    if(b > a - b)   b = a - b;

    LL ans = 1, ca = 1, cb = 1;
    for(LL i = 0; i < b; ++i)
    {
        ca = (ca * (a - i))%p;
        cb = (cb * (b - i))%p;
    }
    ans = (ca*exp_mod(cb, p - 2, p)) % p;
    return ans;
}

LL Lucas(int n, int m, int p)
{
    LL ans = 1;

    while(n&&m&&ans)
    {
        ans = (ans*Comb(n%p, m%p, p)) % p;
        n /= p;
        m /= p;
    }
    return ans;
}

pair<int,LL> DFS(int now)
{

    int sum=0;
    LL ans=1;
    vector<pair<int,LL> > S;
    for(int i=0; i<V[now].size(); i++)
    {
        int v=V[now][i];
        pair<int,LL> p=DFS(v);
        sum+=p.first;
        S.push_back(p);
    }
    int tm=sum;
    for(int i=0; i<S.size(); i++)
    {
        int a1=S[i].first;
        LL a2=S[i].second;
        LL pq=Lucas(tm,a1,MOD);
        ans=((pq*a2)%MOD)*ans%MOD;
        tm-=a1;
    }
    return make_pair(sum+1,ans);
}
void play()
{
    pair<int,LL> p=DFS(0);
    printf("%lld\n",p.second);
}
int T;
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        init();
        play();
    }
//   cout << "Hello world!" << endl;
    return 0;
}