import sys sys.setrecursionlimit(10**7) def I(): return int(sys.stdin.readline().rstrip()) def MI(): return map(int,sys.stdin.readline().rstrip().split()) def LI(): return list(map(int,sys.stdin.readline().rstrip().split())) def LI2(): return list(map(int,sys.stdin.readline().rstrip())) def S(): return sys.stdin.readline().rstrip() def LS(): return list(sys.stdin.readline().rstrip().split()) def LS2(): return list(sys.stdin.readline().rstrip()) def matrix_multiplication(A,B): l = len(A) m = len(B) n = len(B[0]) C = [[0]*n for _ in range(l)] for i in range(l): for j in range(n): for k in range(m): C[i][j] |= A[i][k] & B[k][j] return C def matrix_power(A,n): l = len(A) C = [[0]*l for _ in range(l)] for i in range(l): C[i][i] = 1 while n > 0: if n % 2 == 1: C = matrix_multiplication(C,A) A = matrix_multiplication(A,A) n >>= 1 return C N,M,T = MI() Graph = [[0]*N for _ in range(N)] for _ in range(M): a,b = MI() Graph[a][b] = 1 X = matrix_power(Graph,T) initial_state = [[1]]+[[0]]*(N-1) ANS = matrix_multiplication(X,initial_state) ans = 0 for i in range(N): ans += ANS[i][0] print(ans)