def fib(n, memo=[])
  memo[n] if memo[n]

  if n <= 1
    memo[n] = 1
  else
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
  end

  memo[n]
end

if $PROGRAM_NAME == __FILE__
  puts fib(gets.to_i)
end