#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7,N=205;
struct matrix
{
    int n,m;
    int A[N][N];
    matrix(int _n,int _m)
    {
        n=_n;
        m=_m;
        memset(A,0,sizeof(A));
    }
    matrix operator*(const matrix &e) const
    {
        matrix f(n,e.m);
        for(int a=0;a<f.n;a++){
            for(int b=0;b<f.m;b++){
                for(int c=0;c<m;c++){
                    f.A[a][b]+=A[a][c]*e.A[c][b];
                    f.A[a][b]%=mod;
                }
            }
        }
        return f;
    }
    matrix operator^(int k) const
    {
        matrix res(n,n);
        for(int a=0;a<n;a++){
            res.A[a][a]=1;
        }
        matrix mul=*this;
        while(k>0){
            if(k&1) res=res*mul;
            mul=mul*mul;
            k/=2;
        }
        return res;
    }
};
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    int n, m, q;
    cin >> n >> m >> q;
 
    matrix A(n,n);
 
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        u--, v--;
        A.A[u][v] = 1; // Directed edge
    }
 
 
    while (q--) {
        int s, t, k;
        cin >> s >> t >> k;
        s--, t--;
		A=A^k;
 
        cout << A.A[s][t] << '\n';
    }
}
 

I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKI2RlZmluZSBpbnQgbG9uZyBsb25nCmNvbnN0IGludCBtb2Q9MWU5KzcsTj0yMDU7CnN0cnVjdCBtYXRyaXgKewogICAgaW50IG4sbTsKICAgIGludCBBW05dW05dOwogICAgbWF0cml4KGludCBfbixpbnQgX20pCiAgICB7CiAgICAgICAgbj1fbjsKICAgICAgICBtPV9tOwogICAgICAgIG1lbXNldChBLDAsc2l6ZW9mKEEpKTsKICAgIH0KICAgIG1hdHJpeCBvcGVyYXRvciooY29uc3QgbWF0cml4ICZlKSBjb25zdAogICAgewogICAgICAgIG1hdHJpeCBmKG4sZS5tKTsKICAgICAgICBmb3IoaW50IGE9MDthPGYubjthKyspewogICAgICAgICAgICBmb3IoaW50IGI9MDtiPGYubTtiKyspewogICAgICAgICAgICAgICAgZm9yKGludCBjPTA7YzxtO2MrKyl7CiAgICAgICAgICAgICAgICAgICAgZi5BW2FdW2JdKz1BW2FdW2NdKmUuQVtjXVtiXTsKICAgICAgICAgICAgICAgICAgICBmLkFbYV1bYl0lPW1vZDsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICByZXR1cm4gZjsKICAgIH0KICAgIG1hdHJpeCBvcGVyYXRvcl4oaW50IGspIGNvbnN0CiAgICB7CiAgICAgICAgbWF0cml4IHJlcyhuLG4pOwogICAgICAgIGZvcihpbnQgYT0wO2E8bjthKyspewogICAgICAgICAgICByZXMuQVthXVthXT0xOwogICAgICAgIH0KICAgICAgICBtYXRyaXggbXVsPSp0aGlzOwogICAgICAgIHdoaWxlKGs+MCl7CiAgICAgICAgICAgIGlmKGsmMSkgcmVzPXJlcyptdWw7CiAgICAgICAgICAgIG11bD1tdWwqbXVsOwogICAgICAgICAgICBrLz0yOwogICAgICAgIH0KICAgICAgICByZXR1cm4gcmVzOwogICAgfQp9OwpzaWduZWQgbWFpbigpIHsKICAgIGlvczo6c3luY193aXRoX3N0ZGlvKDApOwogICAgY2luLnRpZSgwKTsKCiAgICBpbnQgbiwgbSwgcTsKICAgIGNpbiA+PiBuID4+IG0gPj4gcTsKCiAgICBtYXRyaXggQShuLG4pOwoKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbTsgaSsrKSB7CiAgICAgICAgaW50IHUsIHY7IGNpbiA+PiB1ID4+IHY7CiAgICAgICAgdS0tLCB2LS07CiAgICAgICAgQS5BW3VdW3ZdID0gMTsgLy8gRGlyZWN0ZWQgZWRnZQogICAgfQoKCiAgICB3aGlsZSAocS0tKSB7CiAgICAgICAgaW50IHMsIHQsIGs7CiAgICAgICAgY2luID4+IHMgPj4gdCA+PiBrOwogICAgICAgIHMtLSwgdC0tOwoJCUE9QV5rOwoKICAgICAgICBjb3V0IDw8IEEuQVtzXVt0XSA8PCAnXG4nOwogICAgfQp9Cg==

MyA0IDQKMSAyCjIgMwozIDEKMiAxCjEgMiA2CjMgMyA1CjEgMyAxCjMgMiA1NAo=

3 4 4
1 2
2 3
3 1
2 1
1 2 6
3 3 5
1 3 1
3 2 54