#------------------------------------------------------------------------------
#  Fibonacci4.py
#  Use a dictionary to save values already known, this time without
#  a global variable.
#------------------------------------------------------------------------------


def fib(n, known):
   if n in known:
      return known[n]
   else:
      known[n] = fib(n-1, known) + fib(n-2, known)
   # end if-else
   return known[n]
# end fib()


def main():
   # Known values
   K = {0:0, 1:1}

   # print(fib(100))
   print(fib(500, K))
   # print(fib(998))
   # print(fib(999)) # finally too big
# end main()

if __name__=='__main__': 
   main() 
# end if