#include #define rep(i, n) for (int i = 0; i < (int)n; ++i) #define rrep(i, n) for (int i = (int)n-1; i >= 0; --i) using namespace std; using ll = long long; template inline bool chmax(T& a, const T& b) { if (a < b){ a = b; return true; } return false; } template inline bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } return false; } /** * @brief 多次元 vector の作成 * @author えびちゃん */ namespace detail { template auto make_vec(vector& sizes, T const& x) { if constexpr (N == 1) { return vector(sizes[0], x); } else { int size = sizes[N-1]; sizes.pop_back(); return vector(size, make_vec(sizes, x)); } } } template auto make_vec(int const(&sizes)[N], T const& x = T()) { vector s(N); for (int i = 0; i < N; ++i) s[i] = sizes[N-i-1]; return detail::make_vec(s, x); } __attribute__((constructor)) void fast_io() { ios::sync_with_stdio(false); cin.tie(nullptr); } template struct matrix { using vec = vector; using mat = vector; mat M; matrix(size_t r, size_t c) : M(r, vec(c)) {} matrix(mat M) : M(M) {} size_t size() const { return M.size();} vec& operator[](size_t i) { return M[i];} const vec& operator[](size_t i) const { return M[i];}; static matrix cross(const matrix& A, const matrix& B) { matrix res(A.size(), B[0].size()); for (int i = 0; i < (int)A.size(); ++i) for (int j = 0; j < (int)B[0].size(); ++j) for (int k = 0; k < (int)B.size(); ++k) res[i][j] |= A[i][k] & B[k][j]; return res; } static matrix identity(size_t n) { matrix res(n, n); for (int i = 0; i < (int)n; ++i) res[i][i] = 1; return res; } matrix pow(long long n) const { matrix A(M), res = identity(size()); while (n > 0) { if (n & 1) res = cross(res, A); A = cross(A, A); n >>= 1; } return res; } }; int main() { int n, m; ll t; cin >> n >> m >> t; matrix mat(n, n); rep(i, m) { int a, b; cin >> a >> b; mat[b][a] = 1; } mat = mat.pow(t); int ans = 0; rep(i, n) ans += mat[0][i]; cout << ans << '\n'; }