## Fibonacci Sequence

View as PDF

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type

The Fibonacci sequence is a well known sequence of numbers in which Given a number  , find the Fibonacci number, modulo  .

Note: For 30% of the marks of this problem, it is guaranteed that .

#### 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. 16, 2014, 1:16 a.m. edit 2

The problem requires you to output mod . That means that you need to get the remainder of the final answer when it is divided by . This operation can be done in Python, C++, and Java by using %.

Example:
999999999999999999999999 mod 1000000007
is 999999999999999999999999 % 1000000007
which is equal to 48999999.
Because 999999999999999999999999 = 999999993000000 * 1000000007 + 48999999,
48999999 is 999999999999999999999999 (mod 1000000007).

It may interest you to know that is a prime number.

There are two highly useful properties of modular arithmetic we often use in programming competitions (% has the same precedence as multiplication and division): • commented on Sept. 13, 2014, 8:30 p.m. edited

This problem is a lot more difficult than it may appear. There is a reason for 15 points. The input can be as big as .