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 .