class BitAndOrSquareMatrix
    attr_reader :rows, :n
    def initialize(*rows)
        @rows, @n = rows, rows.size
    end
    
    def [](i, j)
        @rows[i][j]
    end
    
    def *(other)
        BitAndOrSquareMatrix.new(*(0 ... @n).map { |i|
            (0 ... @n).map { |j|
                (0 ... @n).inject(0) { |prod, k| prod | self[i, k] & other[k, j] }
            }
        })
    end
    
    def **(e)
        x = self
        r = BitAndOrSquareMatrix.new(*(0 ... @n).map { |i| (0 ... @n).map { |j| (i == j) ? 1 : 0 } })
        while e > 0
            r *= x if e.odd?
            x *= x
            e >>= 1
        end
        r
    end
end

N, M, T = gets.split.map(&:to_i)
rows = Array.new(N) { [0] * N }
M.times do
    a, b = gets.split.map { |s| s.to_i - 1 }
    rows[b][a] = 1
end
matrix = BitAndOrSquareMatrix.new(*rows)
result = matrix ** T

puts (0 ... N).sum { |i| result[i, 0] }