# Fibinacci series:
# the sum of two elements defines the next

previous = {0:1L, 1:1L}

def fibonacci(n):
  if previous.has_key(n):
    return previous[n]
  else:
    newValue = fibonacci(n-1) + fibonacci(n-2)
    previous[n] = newValue
    return newValue 


"""
def fibonacci (n):
    if n == 0 or n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

"""

'''
a, b = 0, 1
print a
while b < 1000000:
	print b
	a, b = b, a+b
'''