#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll modulo=1e9+7;

vector<vector<ll>> mult(vector<vector<ll>> a, vector<vector<ll>> b){
    vector<vector<ll>> resp(a.size());

    for(int i=0; i<a.size(); i++){
        for(int j=0; j<b[0].size(); j++){
            ll num=0;

            for(int k=0; k<b.size(); k++){
                ll qtd=(a[i][k]*b[k][j])%modulo;
                num=(num+qtd)%modulo;
            }

            resp[i].push_back(num);
        }
    }

    return resp;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, m, q;
    vector<vector<ll>> graph[32], base;
    cin >> n >> m >> q;
    graph[0].resize(n);
    base.resize(n);

    for(int i=0; i<n; i++){
        graph[0][i].resize(n);
        base[i].resize(n);
        base[i][i]=1;
    }

    for(int i=0; i<m; i++){
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        graph[0][u][v]=1;
    }

    for(int i=1; i<=29; i++){
        graph[i]=mult(graph[i-1], graph[i-1]);
    }

    while(q--){
       int u, v, k;
       cin >> u >> v >> k;
       u--;
       v--;
       vector<vector<ll>> paths=base;

       for(int i=0; k>=(1<<i); i++){
            if(k&(1<<i)){
                paths=mult(paths, graph[i]);
            }
       }

       cout << paths[u][v] << '\n';
    }

    return 0;
}