def fib(n):
if n == 0: return 0
if n == 1: return 1
else:
return fib(n-1)*fib(n-2)
def fib(n):
if n == 0: return 0
if n == 1: return 1
memo = dict()
memo[0] = 0
memo[1] = 1
v = idx = 1
while idx < n:
v = memo[idx - 1] * memo[idx - 2]
return v