#include using namespace std; #define rep(i, n) for(int i = 0; i < n; i++) #define rep2(i, x, n) for(int i = x; i <= n; i++) #define rep3(i, x, n) for(int i = x; i >= n; i--) #define each(e, v) for(auto &e: v) #define pb push_back #define eb emplace_back #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define sz(x) (int)x.size() using ll = long long; using pii = pair; using pil = pair; using pli = pair; using pll = pair; const int MOD = 1000000007; //const int MOD = 998244353; const int inf = (1<<30)-1; const ll INF = (1LL<<60)-1; template bool chmax(T &x, const T &y) {return (x < y)? (x = y, true) : false;}; template bool chmin(T &x, const T &y) {return (x > y)? (x = y, true) : false;}; struct io_setup{ io_setup(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout << fixed << setprecision(15); } } io_setup; template struct Mod_Int{ int x; Mod_Int() : x(0) {} Mod_Int(ll y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {} Mod_Int &operator += (const Mod_Int &p){ if((x += p.x) >= mod) x -= mod; return *this; } Mod_Int &operator -= (const Mod_Int &p){ if((x += mod - p.x) >= mod) x -= mod; return *this; } Mod_Int &operator *= (const Mod_Int &p){ x = (int) (1LL * x * p.x % mod); return *this; } Mod_Int &operator /= (const Mod_Int &p){ *this *= p.inverse(); return *this; } Mod_Int &operator ++ () {return *this += Mod_Int(1);} Mod_Int operator ++ (int){ Mod_Int tmp = *this; ++*this; return tmp; } Mod_Int &operator -- () {return *this -= Mod_Int(1);} Mod_Int operator -- (int){ Mod_Int tmp = *this; --*this; return tmp; } Mod_Int operator - () const {return Mod_Int(-x);} Mod_Int operator + (const Mod_Int &p) const {return Mod_Int(*this) += p;} Mod_Int operator - (const Mod_Int &p) const {return Mod_Int(*this) -= p;} Mod_Int operator * (const Mod_Int &p) const {return Mod_Int(*this) *= p;} Mod_Int operator / (const Mod_Int &p) const {return Mod_Int(*this) /= p;} bool operator == (const Mod_Int &p) const {return x == p.x;} bool operator != (const Mod_Int &p) const {return x != p.x;} Mod_Int inverse() const { assert(*this != Mod_Int(0)); return pow(mod-2); } Mod_Int pow(ll k) const{ Mod_Int now = *this, ret = 1; for(; k; k >>= 1, now *= now){ if(k&1) ret *= now; } return ret; } friend ostream &operator << (ostream &os, const Mod_Int &p){ return os << p.x; } friend istream &operator >> (istream &is, Mod_Int &p){ ll a; is >> a; p = Mod_Int(a); return is; } }; using mint = Mod_Int; template struct Matrix{ vector> A; Matrix(int n, int m) : A(n, vector(m, 0)) {} //+の単位元 int height() const {return sz(A);} int width() const {return sz(A.front());} inline const vector &operator [] (int k) const {return A[k];} inline vector &operator [] (int k) {return A[k];} static Matrix I(int l){ Matrix ret(l, l); rep(i, l) ret[i][i] = 1; //*の単位元 return ret; } Matrix &operator *= (const Matrix &B){ int n = height(), m = width(), p = B.width(); assert(m == B.height()); Matrix tmp(n, p); rep(i, n){ rep(k, m){ rep(j, p) tmp.A[i][j] += A[i][k]*B[k][j]; } } swap(A, tmp.A); return *this; } Matrix operator * (const Matrix &B) const {return Matrix(*this) *= B;} Matrix pow(ll k) const{ int n = height(), m = width(); assert(n == m); Matrix now = *this, ret = I(n); while(k){ if(k&1) ret *= now; now *= now, k >>= 1; } return ret; } bool eq(const T &a, const T &b) const{ return a == b; //return abs(a-b) <= EPS; } pair normalize(){ int n = height(), m = width(), check = 0, rank = 0; T det = 1; rep(j, m){ int pivot = check; rep2(i, check, n-1){ if(A[i][j] != 0) pivot = i; //if(abs(A[i][j]) > abs(A[pivot][j])) pivot = i; } if(check != pivot) det *= T(-1); swap(A[check], A[pivot]); if(eq(A[check][j], 0)) {det = T(0); continue;} rank++; det *= A[check][j]; rep2(k, j+1, m-1) A[check][k] /= A[check][j]; A[check][j] = 1; rep(i, n){ if(i == check) continue; rep2(k, j+1, m-1) A[i][k] -= A[i][j]*A[check][k]; A[i][j] = 0; } if(++check == n) break; } return make_pair(rank, det); } vector> Gausiann_elimination(const vector &b){ int n = height(), m = width(); assert(sz(b) == n); rep(i, n) A[i].pb(b[i]); normalize(); vector> ret; vector p(n, m+1); vector is_zero(m, true); rep(i, n){ rep(j, m+1){ if(!eq(A[i][j], 0)) {p[i] = j; break;} } if(p[i] < m) is_zero[p[i]] = false; if(p[i] == m) return ret; } vector basis(m, 0); rep(i, n){ if(p[i] < m) basis[p[i]] = A[i][m]; } ret.pb(basis); rep(j, m){ if(!is_zero[j]) continue; basis[j] = 1; rep(i, n){ if(p[i] < m) basis[p[i]] = -A[i][j]; } ret.pb(basis), basis[j] = 0; } return ret; } }; int main(){ int N, M; ll T; cin >> N >> M >> T; using mint1 = Mod_Int; using mint2 = Mod_Int<998244353>; using mint3 = Mod_Int<998244853>; Matrix A(N, N), X(N, 1); Matrix B(N, N), Y(N, 1); Matrix C(N, N), Z(N, 1); rep(i, M){ int x, y; cin >> x >> y; A[x][y] = 1, B[x][y] = 1, C[x][y] = 1; } X[0][0] = 1, Y[0][0] = 1, Z[0][0] = 1; A = A.pow(T), B = B.pow(T), C = C.pow(T); A *= X, B *= Y, C *= Z; int ans = 0; rep(i, N){ if(A[i][0] != 0 || B[i][0] != 0 || C[i][0] != 0) ans++; } cout << ans << '\n'; }