Fibonacci Sequence (Harder)

View as PDF

Submit solution

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

Author:
Problem type

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

26

Sample Output

121393

Comments


  • 1
    dchoo333  commented on Sept. 3, 2021, 7:41 p.m.

    What's different about this problem to the simpler one?


    • 2
      _wcipeg  commented on Sept. 3, 2021, 8:04 p.m.

      The highest possible value for N can be greater than the one in the simpler version.


      • 1
        dchoo333  commented on Sept. 4, 2021, 1:38 a.m.

        Where can I find a Python 3 explanation for this problem?


  • 1
    enigma_one  commented on Aug. 8, 2021, 4:05 p.m.

    Where can I find editorial with explanation for this problem?


    • 2
      Plasmatic  commented on Aug. 8, 2021, 5:05 p.m.

      • 1
        enigma_one  commented on Aug. 11, 2021, 12:13 a.m.

        Thank you, but I got AC already. I was confused about the Pisano period, but that's not required in this question. Store n in string and use matrix exponentiation properly :)

        A hint is : if you know the answer for n=500 in matrix X, u can get an answer for n=5000 by X^(10) :)


  • 1
    RAiNcalleER  commented on July 11, 2021, 7:03 p.m.

  • 1
    princeMishra  commented on July 9, 2021, 8:19 a.m.

    study PISANO number for fibonacci numbers and also solve https://www.spoj.com/problems/PISANO/cstart=10


  • 2
    ishank162  commented on April 27, 2021, 7:24 a.m.

  • -21
    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.