import sys import numpy as np read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines def mult(A, B): C = np.dot(A, B) C[C >= 1] = 1 return C def mat_pow(A, n): if n == 0: return np.eye(len(A), dtype=np.int64) X = mat_pow(A, n // 2) X = mult(X, X) return mult(A, X) if n & 1 else X N, M, T = map(int, readline().split()) A = np.zeros((N, N), np.int64) m = map(int, read().split()) for frm, to in zip(m, m): A[to, frm] += 1 B = mat_pow(A, T) ans = B[:, 0].sum() print(ans)