Question
Last two digit Fibonacci
Given a number N. Find the last two digits of the Nth Fibonacci number.
Note: If the last two digits are 02, return 2.
Note: If the last two digits are 02, return 2.
Input
There is a single line of input that takes an integer as input representing Nth Fibonacci number.
Constraints:
1 ≤ N ≤ 1018
Constraints:
1 ≤ N ≤ 1018
Output
Print a single integer representing the last two digits of Nthe Fibonacci number.
Example
Input:
13
Output:
33
Explanation:
The 13th Fibonacci number is 233.
So the last two digits are 3 and 3.
Input:
255
Output:
70
Explanation:
The 255th Fibonacci number is 87571595343018854458033386304178158174356588264390370.
Thus, the last two digits are 7 and 0.
13
Output:
33
Explanation:
The 13th Fibonacci number is 233.
So the last two digits are 3 and 3.
Input:
255
Output:
70
Explanation:
The 255th Fibonacci number is 87571595343018854458033386304178158174356588264390370.
Thus, the last two digits are 7 and 0.