#include <cstdio>
#include <cstring>
#include <algorithm>
#include <ctime>
#include <queue>

using namespace std;

#define MAXN 100010
#define INF 0x3f3f3f3f
#define mo 1000000007
#define MIN(a,b) (a<b?a:b)
typedef long long LL;

#define MAX(a,b) (a>b?a:b)
#define MIN(a,b) (a<b?a:b)

int n,m,k,tree[MAXN*4],e[MAXN];
vector<int> adj[MAXN];

void Build(int i,int l,int r)
{
    if(l==r){
        tree[i]=e[l];
        return;
    }
    int mid=(l+r)>>1;
    Build(i*2,l,mid);
    Build(i*2+1,mid+1,r);
    tree[i]=MIN(tree[i*2],tree[i*2+1]);
}

void Modify(int i,int l,int r,int p)
{
    if(l==r){
        tree[i]=e[l];
        return;
    }
    int mid=(l+r)>>1;
    if(p<=mid) Modify(i*2,l,mid,p);
    else Modify(i*2+1,mid+1,r,p);
    tree[i]=MIN(tree[i*2],tree[i*2+1]);
}

int Getans(int i,int l,int r)
{
    if(l==r) return r;
    int mid=(l+r)>>1;
    return tree[i*2]<=k?Getans(i*2,l,mid):Getans(i*2+1,mid+1,r);
}

void Init()
{
    memset(e,0,sizeof(e));
    int i,u,v;
    scanf("%d%d%d",&n,&m,&k);
    for(i=1;i<=n;++i) adj[i].clear();
    for(i=1;i<=m;++i){
        scanf("%d%d",&u,&v);
        adj[u].push_back(v); ++e[v];
    }
}

void Solve()
{
    int i,j,u,v,ans=0;
    for(i=1;i<=n;++i){
        u=Getans(1,1,n); ans=(1LL*i*u+ans)%mo;
        k-=e[u]; e[u]=INF; Modify(1,1,n,u);
        for(j=0;j<(int)adj[u].size();++j){
            v=adj[u][j];
            if(e[v]==INF) continue;
            --e[v]; Modify(1,1,n,v);
        }
    }
    printf("%d\n",ans);
}

int main ()
{
    int t;
    for(scanf("%d",&t);t;--t){
        Init();
        Build(1,1,n);
        Solve();
    }
    return 0;
}