Extended Fibonacci Numbers

Time limit2sMemory limit128 MB

Summary

Compute the sign and absolute value modulo 1e9 of the Fibonacci sequence extended to negative indices for a given n up to 1,000,000 in absolute value.

Level: Easy3 of 10
Topics: Math, Implementation
Solved: No attempts yet

Problem

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)).

Input

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

Output

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).

Examples4

Example 1
Input
```
-2
```
Expected output
```
-1
1
```
Example 2
Input
```
0
```
Expected output
```
0
0
```
Example 3
Input
```
10
```
Expected output
```
1
55
```
Example 4
Input
```
-7
```
Expected output
```
1
13
```