### PROBLEM LINK:

**Author:** Suraj Kumar

**Tester:** Priyanshu Jain

### DIFFICULTY:

EASY

### PREREQUISITES:

Matrix form of Fibonacci numbers, Binary exponentiation.

### PROBLEM:

You just need to find the nth Fibonacci number modulo 10^9+7.

### EXPLANATION:

It is a 2x2 matrix A with A[0][0]=1, A[0][1]=1, A[1][0]=1, A[1][1]=0. With this matrix form one can calculate the nth

Fibonacci just by raising the matrix to the power n. A[0][1] 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.