def exp(n, k)
    x = 1   
    r = n 
    while k > 0 
        x *= r if k & 1 == 1
        r *= r    
        k >>= 1
    end 
    x   
end

require 'matrix'
p (exp(Matrix[[1, 1], [1, 0]], gets.to_i) * Vector[1, 0])[0]