Fibonacci Sequence (Harder)

View as PDF

Submit solution

Points: 20
Time limit: 0.3s
Memory limit: 64M

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 (1 \le N \le 10^{100\,000}), find the N^{th} Fibonacci number, modulo 1\,000\,000\,007 (= 10^9 + 7).

Input Specification

The first line of input will have the number N.

Output Specification

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

Sample Input


Sample Output



  • -15
    Abhishek05  commented on March 8, 2020, 10:06 p.m. edited

    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.