#------------------------------------------------------------------------------
#  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()


# function main() -------------------------------------------------------------
def main():

   # Known values
   K = {0:0, 1:1}

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

# end main()

# closing conditional ---------------------------------------------------------
if __name__=='__main__':

   main()

# end