Informatica Online Judge

  n번째 피보나치 수 (Hell) [0982 / 03D6]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 229   Total Tried : 2853


The Champion of this Problem (C++) : gs17003 - ms / 457byte
My Best Submission (C++) : N/A

[JKJeong 2014]

Background

피보나치 수에 대한 문제는 많이 풀어보았을 것이다.

f0 = 1, f1 = 1로 시작하는 피보나치 수의 n번째 항을 구하는 프로그램을 작성하시오.

단, n이 너무 커지기 때문에 피보나치 수를 100,000,007로 나눈 나머지를 출력하시오.

Input

첫 번째 줄에 입력값 n이 입력된다.

[입력값의 정의역]
1 <= n <= 10,000,000,000

Output

n번째 피보나치수를 100,000,007로 나눈 나머지를 출력한다.

IO Example

입력
2

출력
2

입력2
9

출력2
55

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]