from functools import lru_cache

@lru_cache(maxsize=1000)
def fibc(n):
	if n < 2:
		return 1
	else:
		return fibc(n-1)+fibc(n-2)


def fibs(n):
	i = 1
	a = 1
	b = 1
	while i < n:
		(a,b) = (b,a+b)
		i+=1
	return b

print(fibc(1000))
print(fibs(1000))