피보나치 수의 확장

시간 제한2초메모리 제한128 MB

요약

음수 인덱스까지 확장된 피보나치 수열에서 주어진 n(|n|≤1,000,000)에 대해 F(n)의 부호와 절댓값을 1,000,000,000으로 나눈 나머지를 구하는 문제입니다.

난이도: 쉬움10점 중 3점
유형: 수학, 구현
정답자: 아직 제출이 없습니다

문제

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

$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)으로 나눈 나머지를 출력한다.

예제4

예제 1
입력
```
-2
```
예상 출력
```
-1
1
```
예제 2
입력
```
0
```
예상 출력
```
0
0
```
예제 3
입력
```
10
```
예상 출력
```
1
55
```
예제 4
입력
```
-7
```
예상 출력
```
1
13
```