Points: 15 (partial)
Time limit: 1.0s
Memory limit: 64M
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 .
The first line of input will have the number .
The Fibonacci number, modulo .
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
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):
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 .