#line 2 "/Users/tiramister/CompetitiveProgramming/Cpp/CppLibrary/Number/matrix.hpp"

#include <vector>

template <class T>
struct Matrix : public std::vector<std::vector<T>> {
    // constructor
    using std::vector<std::vector<T>>::vector;

    Matrix(int h, int w, T val = 0) {
        this->resize(h);
        for (auto& v : *this) v.resize(w, val);
    }

    static Matrix id(int n) {
        Matrix m(n, n);
        for (int i = 0; i < n; ++i) m[i][i] = 1;
        return m;
    }

    // arithmetic
    Matrix operator*(const Matrix& m) const { return Matrix(*this) *= m; }
    Matrix& operator*=(const Matrix& m) {
        int h1 = this->size(),
            h2 = m.size(),
            w2 = m.front().size();

        Matrix nmat(h1, w2);
        for (int i = 0; i < h1; ++i) {
            for (int j = 0; j < w2; ++j) {
                for (int k = 0; k < h2; ++k) {
                    nmat[i][j] += (*this)[i][k] * m[k][j];
                }
            }
        }
        return *this = nmat;
    }

    template <class U>
    Matrix pow(U k) {
        Matrix ret = id(this->size());
        Matrix a = *this;

        while (k > 0) {
            if (k & 1) ret *= a;
            a *= a;
            k >>= 1;
        }
        return ret;
    }
};
#line 2 "main.cpp"
#include <atcoder/modint>
#include <iostream>
#line 5 "main.cpp"

using namespace std;
using lint = long long;
using mint = atcoder::static_modint<1000000009>;

void solve() {
    int n, m;
    lint t;
    cin >> n >> m >> t;

    Matrix<mint> mat(n, n, 0);
    while (m--) {
        int u, v;
        cin >> u >> v;
        mat[u][v] = 1;
    }
    mat = mat.pow(t);

    int ans = 0;
    for (int v = 0; v < n; ++v) {
        if (mat[v][0] != 0) ++ans;
    }
    cout << ans << "\n";
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    solve();

    return 0;
}