n = gets.to_i
@memo = []
def fibonacci(n)
  @memo[n] ||= if n == 1 || n == 0
                  1
                else
                  fibonacci(n-2) + fibonacci(n-1)
                end
end

fibonacci(n)
p @memo[n]

