Extended Fibonacci Numbers

The Fibonacci numbers are defined as follows.

$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}$

This definition is normally used for nonnegative integers (n). We can extend it to negative indices by requiring the recurrence (F(n)=F(n-1)+F(n-2)) to keep holding even when (n \le 1). For example, when (n=1), the equality (F(1)=F(0)+F(-1)) must hold, so (F(-1)=1).

Given an integer (n), determine the sign and absolute value of (F(n)).

The first line contains an integer (n). It satisfies (|n| \le 1,000,000).

On the first line, print 1 if (F(n)) is positive, 0 if it is zero, and -1 if it is negative.

On the second line, print (|F(n)|) modulo (1,000,000,000).