/* ***********************************************
Author        :kuangbin
Created Time  :2016/3/5 19:49:11
File Name     :F:\ACM\2016ACM\BestCoder\BC74\C.cpp
************************************************ */

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;

const int MAXN = 100010;
const int INF = 0x3f3f3f3f;
struct Node {
    int l,r;
    int Min;
}segTree[MAXN<<2];
int a[MAXN];
void build(int i,int l,int r) {
    segTree[i].l = l;
    segTree[i].r = r;
    if (l == r) {
        segTree[i].Min = a[l];
        return;
    }
    int mid = (l+r)/2;
    build(i<<1,l,mid);
    build((i<<1)|1,mid+1,r);
    segTree[i].Min = min(segTree[i<<1].Min,segTree[(i<<1)|1].Min);
}


void update(int i,int id,int val) {
    if (segTree[i].l == id && segTree[i].r == id) {
        segTree[i].Min = val;
        return;
    }
    int mid = (segTree[i].l + segTree[i].r)/2;
    if (id <= mid)update(i<<1,id,val);
    else update((i<<1)|1,id,val);
    segTree[i].Min = min(segTree[i<<1].Min,segTree[(i<<1)|1].Min);
}

int query(int i,int val) {
    if(segTree[i].l == segTree[i].r)
        return segTree[i].l;
    if (segTree[i<<1].Min <= val)return query(i<<1,val);
    else return query((i<<1)|1,val);
}

int head[MAXN];
struct Edge{
    int to,next;
}edge[MAXN*2];
int tot;

void add(int u,int v) {
    edge[tot].to = v;
    edge[tot].next = head[u];
    head[u] = tot++;
    a[v]++;
}


const int MOD = 1e9+7;

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int T;
    int n,m,k;
    scanf("%d",&T);
    while(T--) {
        scanf("%d%d%d",&n,&m,&k);
        tot = 0;
        for(int i = 1;i <= n;i++) {
            a[i] = 0;
            head[i] = -1;
        }
        int u,v;
        for(int i = 0;i < m;i++) {
            scanf("%d%d",&u,&v);
            add(u,v);
        }
        build(1,1,n);
        long long ans = 0;
        for(int j = 1;j <= n;j++) {
            int id = query(1,k);
            ans = (ans + (long long)j*id)%MOD;
            k -= a[id];
            a[id] = INF;
            update(1,id,INF);
            for(int i = head[id];i != -1;i = edge[i].next) {
                v = edge[i].to;
                if (a[v] == INF)continue;
                a[v]--;
                update(1,v,a[v]);
            }
        }
        printf("%d\n",(int)ans);
    }
    return 0;
}