Fibonacci Sequence (Harder)

Points: 20

Time limit: 0.3s

Memory limit: 64M

Author:

Problem type

Allowed languages

Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, ~~CommonLisp~~, D, Dart, F#, Forth, Fortran, Go, ~~Groovy~~, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, ~~Nim~~, ~~ObjC~~, OCaml, ~~Octave~~, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

quantum is not feeling well today, and has decided to create a more painful version of the simple Fibonacci problem.

Recall that the Fibonacci sequence is a well known sequence of numbers in which

$\displaystyle F(n) = \begin{cases} 0, & \text{if } n = 0 \\ 1, & \text{if } n = 1 \\ F(n-2) + F(n-1), & \text{if } n \ge 2 \end{cases}$

You are given a number $N$ ~N~ $(1 \le N \le 10^{100\,000})$ ~(1 \le N \le 10^{100\,000})~, find the $N^{th}$ ~N^{th}~ Fibonacci number, modulo $1\,000\,000\,007$ ~1\,000\,000\,007~ $(= 10^9 + 7)$ ~(= 10^9 + 7)~.

Input Specification

The first line of input will have the number $N$ ~N~.

Output Specification

The $N^{th}$ ~N^{th}~ Fibonacci number, modulo $1\,000\,000\,007$ ~1\,000\,000\,007~ $(= 10^9 + 7)$ ~(= 10^9 + 7)~.

Sample Input

Sample Output

Comments

-15

Abhishek05 commented on March 8, 2020, 10:06 p.m. ← edited →

Hmmm I don't know any methods to calculate the nth term without using more than the memory limit other than f(n-2) + f(n-1). Do I require recursion or something of that sort?

This comment is hidden due to too much negative feedback. Click here to view it.

2

31501357 commented on Jan. 23, 2021, 12:38 p.m.

Use math.