Fibonacci Sequence (Harder)

Points: 17

Time limit: 0.3s

Memory limit: 64M

Author:

quantum

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$ ~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

0

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

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

1

_wcipeg commented on Sept. 3, 2021, 8:04 p.m. ← edited →

The highest possible value for $N$ ~N~ can be greater than the one in the simpler version. There is also a lower time limit.

0

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

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

0

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

Where can I find editorial with explanation for this problem?

1

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

solution is this

0

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.

https://usaco.guide/plat/mat-exp?lang=cpp

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.

Last topic might help!!

-23

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. Show it anyway.

2

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

Use math.