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| matrix[i, 0] }