## Fibonacci Sequence (Harder)

View as PDF

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

You are given a number , find the Fibonacci number, modulo .

#### Input Specification

The first line of input will have the number .

#### Output Specification

The Fibonacci number, modulo .

#### Sample Input

26

#### Sample Output

121393

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

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

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

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

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

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

Where can I find editorial with explanation for this problem?

• commented on Aug. 8, 2021, 5:05 p.m.
• 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) :)

• commented on July 11, 2021, 7:03 p.m.
• 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

• commented on April 27, 2021, 7:24 a.m.
• 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.

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

Use math.