// karanaggarwal
#include<bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(a) (int)(a.size())
#define SET(a,b) memset(a,b,sizeof(a))
#define LET(x,a) __typeof(a) x(a)
#define TR(v,it) for( LET(it,v.begin()) ; it != v.end() ; it++)
#define repi(i,n) for(int i=0; i<(int)n;i++)
#define si(n) scanf("%d",&n)
#define sll(n) scanf("%lld",&n)
#define sortv(a) sort(a.begin(),a.end())
#define all(a) a.begin(),a.end()
#define DRT()  int t; cin>>t; while(t--)
#define TRACE
using namespace std;

//FILE *fin = freopen("in","r",stdin);
//FILE *fout = freopen("out","w",stdout);


#ifdef TRACE
#define trace1(x)                cerr << #x << ": " << x << endl;
#define trace2(x, y)             cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
#define trace3(x, y, z)          cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
#define trace4(a, b, c, d)       cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
#define trace5(a, b, c, d, e)    cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
#define trace6(a, b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;

#else

#define trace1(x)
#define trace2(x, y)
#define trace3(x, y, z)
#define trace4(a, b, c, d)
#define trace5(a, b, c, d, e)
#define trace6(a, b, c, d, e, f)

#endif


typedef long long LL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector< PII > VPII;

#define mod 1000000007

LL A[31][31];
LL ret[31][31];
LL og[31][31];
int N; 

void mul(LL A[][31], LL B[][31])
{
    LL C[31][31];
    repi(i,N)
        repi(j,N)
        {
            C[i][j] = 0;
            repi(k,N)
                C[i][j] += (A[i][k]*B[k][j]) % mod;
        }
    repi(i,N)
        repi(j,N)
            A[i][j] = C[i][j]%mod;
}

void power(LL A[][31], LL P)
{
    SET(ret,0); for(int i=0; i<N;i++)ret[i][i] = 1;
    while(P)
    {
        if(P&1)
            mul(ret,A);
        mul(A,A); P/=2;
    }

}

LL ans[30][31][31];

int main()
{
    int M;
    cin>>N>>M;
    LL K;
    cin>>K; int x,y;
    K++;
    while(M--)
    {
        si(x); si(y); x--; y--; A[x][y]++;
    }
    N++;
    repi(i,N)repi(j,N)og[i][j] = A[i][j];

    for(int dest = 0; dest<N-1; dest++)
    {
        repi(i,N)repi(j,N)A[i][j] = og[i][j];
        int y = dest; 
        A[y][N-1] = 1; A[N-1][N-1] = 1;
        power(A,K);
        repi(i,N)repi(j,N)ans[dest][i][j] = ret[i][j];
        ans[y][y][N-1]--; if(ans[y][y][N-1]<0)ans[y][y][N-1]++;
    }

    int q; si(q); while(q--)
    {
        int x,y; si(x); si(y); x--; y--; 
        printf("%lld\n", ans[y][x][N-1]);
    }
    return 0;
}