Memoization simple

F = [0] * 1001

def f(i):
  if F[i] == 0:
    if i < 3:
      F[i] = 1
    else:
      F[i] = (f(i-1) + f(i-2)) % 1000000000
  return F[i]

for i in range(1, 1001):
  print(i, f(i))