10689 - Yet another Number Sequence

Difficulty : medium

Solution Description :

Fibonacci ( Pisano period) number problem

The last digit of Fibonacco number repeats with a period of 60. The last two digits repeat with a period of 300, the last three with a period of 1500 and the last four digits have a period of 15000. (For more information you can search in google about Pisano period).

f(0) = 1*a + 0*b
f(1) = 0*a + 1*b
f(2) = 1*a + 1*b
f(3) = 1*a + 2*b
f(4) = 2*a + 3*b
f(5) = 3*a + 5*b
f(6) = 5*a + 8*b
f(7) = 8*a + 13*b

so, f(n) = Fibonacci_number[n-1]*a + Fibonacci_number[n]*b

You can find Fibonacci_number using the rule of Pisano period.
If m=4 you need to calculate fist 15000 Fibonacci number (you need to store last 4 digit).
If m=3 you need to calculate fist 1500 Fibonacci number (you need to store last 3 digit).
and so on.

I think now the problem very easy.