피보나치 수의 확장

피보나치 수는 다음과 같이 정의된다.

$F(n) := \begin{cases}0 & \text{if }n = 0\text{;} \\\ 1 & \text{if }n = 1\text{;} \\\ F(n-1) + F(n-2) & \text{if }n > 1\text{.} \end{cases}$

일반적으로 이 정의는 0 이상의 정수 (n)에 대해 사용된다. 그러나 점화식 (F(n)=F(n-1)+F(n-2))가 (n \le 1)에서도 계속 성립한다고 두면, 음수 인덱스의 피보나치 수도 자연스럽게 정의할 수 있다. 예를 들어 (n=1)에서 (F(1)=F(0)+F(-1))이어야 하므로 (F(-1)=1)이다.

정수 (n)이 주어졌을 때 (F(n))의 부호와 절댓값을 구하시오.

첫째 줄에 정수 (n)이 주어진다. (|n| \le 1,000,000)이다.

첫째 줄에 (F(n))이 양수이면 1, 0이면 0, 음수이면 -1을 출력한다.

둘째 줄에는 (|F(n)|)을 (1,000,000,000)으로 나눈 나머지를 출력한다.