#------------------------------------------------------------------------------
#  Fibonacci3.py
#  Use a dictionary to save values already known.
#------------------------------------------------------------------------------

known = {0:0, 1:1} # a global variable

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


def main(): 
   # print(fib(100))
   print(fib(500))
   #print(fib(998))
   #print(fib(999)) # finally too big
#end main()

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