#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define mp make_pair
#define pb push_back
#define sqr(a) ((a) * (a))
#define sz(a) int(a.size())
#define all(a) a.begin(), a.end()
#define forn(i, n) for(int i = 0; i < int(n); i++)
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)

typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;

template <class A, class B> ostream& operator << (ostream& out, const pair<A, B> &a) {
    return out << "(" << a.x << ", " << a.y << ")";
}

template <class A> ostream& operator << (ostream& out, const vector<A> &v) {
    out << "[";
    forn(i, sz(v)) {
        if(i) out << ", ";
        out << v[i];
    }
    return out << "]";
}

mt19937 rnd(time(NULL));

const int INF = int(1e9);
const li INF64 = li(1e18);
const int MOD = int(1e9) + 7;
const ld EPS = 1e-9;
const ld PI = acos(-1.0);

struct query{
    int v, k;
};

int n, m, t;
vector<vector<int>> g;
vector<query> q;

bool read () {
    if (!(cin >> n >> m >> t))
        return false;
    g.assign(n, {});
    forn(i, m){
        int v, u;
        cin >> v >> u;
        --v, --u;
        g[v].pb(u);
        g[u].pb(v);
    }
    q.resize(t);
    forn(i, t){
        cin >> q[i].v >> q[i].k;
        --q[i].v;
    }
    return true;
}

int add(int a, int b){
    a += b;
    if (a >= MOD)
        a -= MOD;
    return a;
}

int mul(int a, int b){
    return a * li(b) % MOD;
}

int binpow(int a, int b){
    int res = 1;
    while (b){
        if (b & 1)
            res = mul(res, a);
        a = mul(a, a);
        b >>= 1;
    }
    return res;
}

const int N = 203;

typedef array<array<int, N>, N> mat;

mat operator *(const mat &a, const mat &b){
    mat c;
    forn(i, N) forn(j, N) c[i][j] = 0;
    forn(i, N) forn(j, N) forn(k, N) c[i][j] = add(c[i][j], mul(a[i][k], b[k][j]));
    return c;
}

void solve() {
    vector<mat> sv(25);
    forn(i, N) forn(j, N) sv[0][i][j] = 0;
    forn(v, n) for (int u : g[v]) ++sv[0][v][u];
    forn(i, sz(sv) - 1) sv[i + 1] = sv[i] * sv[i];
    forn(z, t){
        int v = q[z].v, k = q[z].k;
        array<int, N> cur, nw;
        forn(i, N) cur[i] = i < n;
        forn(b, 25) if ((k >> b) & 1){
            forn(i, N) nw[i] = 0;
            forn(i, N) forn(j, N)
                nw[j] = add(nw[j], mul(cur[i], sv[b][i][j]));
            cur = nw;
        }
        cout << cur[v] << '\n';
    }
}

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);

    int tt = clock();
#endif

    cerr.precision(15);
    cout.precision(15);
    cerr << fixed;
    cout << fixed;

#ifdef _DEBUG
    while(read()) {
#else
    if(read()) {
#endif
        solve();

#ifdef _DEBUG
    cerr << "TIME = " << clock() - tt << endl;
    tt = clock();
#endif

    }
}