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

using namespace std;

struct rec{
    int x,y,nxt;
    bool operator < (const rec another) const{
        return y>another.y;
    }
}b[200009],a[200009];
#define mod 1000000007
priority_queue <rec> q;
int readint(){
    int ch=getchar(),ret=0;
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret;
}
int n,m,k,ans[100009],cnt,cur,fir[100009],now[100009];
int d[100009],T;
bool vis[100009];
bool cmp(rec x,rec y){
    return x.y<y.y;
}
void addedge(int from,int to){
    cur++;
    if (fir[from]==0) fir[from]=cur;
    a[cur].y=to;
    a[now[from]].nxt=cur;
    now[from]=cur;
}
int main(){
#ifdef YJQ_LOCAL
    freopen(".in","r",stdin);
#endif
    scanf("%d",&T);
    while(T--){
        memset(a,0,sizeof(a[0])*(cur+1));
        memset(d,0,sizeof(d[0])*(n+1));
        memset(vis,0,sizeof(vis[0])*(n+1));
        memset(fir,0,sizeof(fir[0])*(n+1));
        memset(now,0,sizeof(now[0])*(n+1));
        cur=cnt=0;
        n=readint(),m=readint(),k=readint();
        for (int i=1;i<=m;i++){
            //scanf("%d%d",&b[i].x,&b[i].y);
            b[i].x=readint(),b[i].y=readint();
        }
        sort(b+1,b+1+m);
        for (int i=1;i<=m;i++){
            addedge(b[i].x,b[i].y);
            d[b[i].y]++;
        }
        for (int i=1;i<=n;i++){
            if (k>=d[i] && !vis[i]){
                k-=d[i];
                d[i]=0;
                ans[++cnt]=i;
                vis[i]=1;
                for (int j=fir[i];j;j=a[j].nxt){
                    q.push(a[j]);
                }
            }
            while(!q.empty()){
                rec x=q.top();
                q.pop();
                while(!q.empty() && q.top().y==x.y){
                    if (!vis[x.y]){
                        d[x.y]--;
                    }    x=q.top();
                        q.pop();
                    
                }
                if (d[x.y]) d[x.y]--;
                if (vis[x.y] || x.y>i) continue;
                if (k>=d[x.y]){
                    k-=d[x.y];
                    d[x.y]=0;
                    ans[++cnt]=x.y;
                    vis[x.y]=true;
                    for (int j=fir[x.y];j;j=a[j].nxt){
                        q.push(a[j]);
                    }
                }
            }
        }
        long long ANS=0;
        for (int i=1;i<=n;i++){
            ANS=(ANS+(long long)i*ans[i]) % mod;        
        }
        printf("%I64d\n",ANS);
    }
}