#include<set>
#include<queue>
#include<set>
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)
#define eprintf(s...)  fprintf(stderr, s)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }

const LL MOD = 1e9+7;

int N, M, K;
VI G[100111];
int deg[100111];
bool use[100111];

void MAIN() {
    scanf("%d%d%d", &N, &M, &K);

    REP (i, N) {
    G[i].clear();
    deg[i] = 0;
    use[i] = false;
    }
    REP (i, M) {
    int x, y;
    scanf("%d%d", &x, &y);
    x--; y--;
    G[x].push_back(y);
    deg[y]++;
    }

    priority_queue<int, vector<int>, greater<int> > L;
    REP (i, N) {
    if (deg[i] <= K) {
        L.push(i);
    }
    }

    LL ans = 0;

    REP ($, N) {
    while (use[L.top()] || deg[L.top()] > K) {
        L.pop();
    }

    int v = L.top();
    L.pop();
    K -= deg[v];
    use[v] = true;

    EACH (e, G[v]) if (!use[*e]) {
        deg[*e]--;
        if (deg[*e] <= K) L.push(*e);
    }

    ans = (ans + (LL)($+1) * (v+1)) % MOD;
    }

    printf("%d\n", (int)ans);

}

int main() {
    int T;
    scanf("%d", &T);
    REP (i, T) MAIN();
    return 0;
}