Author: Suraj Kumar
Tester: Priyanshu Jain
Matrix form of Fibonacci numbers, Binary exponentiation.
You just need to find the nth Fibonacci number modulo 10^9+7.
It is a 2x2 matrix A with A=1, A=1, A=1, A=0. With this matrix form one can calculate the nth
Fibonacci just by raising the matrix to the power n. A will give you the nth Fibonacci number.
How to find the answer modulo 10^9+7.
Use the Binary Exponentiation technique. If the number becomes greater than 10^9+7 after the multiplication
then the elements of the matrix is replaced by their modulo 10^9+7.
Click [here](http://www.geeksforgeeks.org/program-for- nth-fibonacci- number/) for more details.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.