백준 1788번 - 피보나치 수의 확장

n = int(input())

def fibo(n):
  a,b=0,1
  for i in range(n):
    a,b=b,(a+b)%1000000000
  return a

if n < 0:
  print(-1 if (-n)%2==0 else 1)
  print(fibo(-n))
elif n == 0:
  print(0)
  print(0)
else:
  print(1)
  print(fibo(n))