Problem Statement | |||||||||||||
Depicted below is the Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... As you can see, each value from 2 on is the sum of the previous two values. Given the 0-based index of a Fibonacci number and an int M, return the index-th Fibonacci number modulo M. | |||||||||||||
Definition | |||||||||||||
| |||||||||||||
Constraints | |||||||||||||
| - | index will be an integer between 0 and 1015, inclusive, with no extra leading zeroes. | ||||||||||||
| - | M will be between 1 and 1000000 (106). | ||||||||||||
Examples | |||||||||||||
| 0) | |||||||||||||
| |||||||||||||
| 1) | |||||||||||||
| |||||||||||||
| 2) | |||||||||||||
| |||||||||||||
| 3) | |||||||||||||
| |||||||||||||
| 4) | |||||||||||||
| |||||||||||||
| 5) | |||||||||||||
| |||||||||||||