#include<stdio.h>
#include<algorithm>
#define P 1000000007
#define inf 1000000000
#define N 200005
#define M 200005
using namespace std;
int i,j,k,l,s,n,m,f[N*4],si[N],ans,tot,x,y,test,v[N];
struct node {
    int next[M],last[N],to[M];
    inline void add(int o,int p) {
        next[++tot]=last[o]; last[o]=tot; to[tot]=p;
    }
}A;
inline void up(int o) {
    f[o]=min(f[o*2],f[o*2+1]);
}
inline void build(int o,int l,int r) {
    if (l==r) {
        f[o]=si[l]; return ;
    }
    int mid=(l+r)>>1;
    build(o*2,l,mid),build(o*2+1,mid+1,r);
    up(o);
}
inline void change(int o,int l,int r,int ll,int p) {
    if (l==ll&&r==ll) {
        f[o]=p; return ;
    }
    int mid=(l+r)>>1;
    if (ll<=mid) change(o*2,l,mid,ll,p);
    else change(o*2+1,mid+1,r,ll,p);
    up(o);
}
inline int ask(int o,int l,int r,int p) {
    if (l==r) return l;
    int mid=(l+r)>>1;
    if (f[o*2]<=p) return ask(o*2,l,mid,p);
    else return ask(o*2+1,mid+1,r,p);
}

int main() {
    scanf("%d",&test);
    while (test--) {
        scanf("%d%d%d",&n,&m,&k);
        for (i=1;i<=n;i++) si[i]=v[i]=0,A.last[i]=v[i]=0;
        ans=tot=0;
        for (i=1;i<=m;i++) scanf("%d%d",&x,&y),A.add(x,y),si[y]++;
        build(1,1,n);
        for (i=1;i<=n;i++) {
            int gt=ask(1,1,n,k);
            (ans+=1ll*i*gt%P)%=P;
            k-=si[gt]; v[gt]=1;
            change(1,1,n,gt,inf);
            for (j=A.last[gt];j;j=A.next[j]) if (!v[A.to[j]]) change(1,1,n,A.to[j],--si[A.to[j]]);
        }
        printf("%d\n",ans);
    }
}