# Nth Fibonacci Number

Given a positive integer n, find the nth fibonacci number. Since the answer can be very large, return the answer modulo 1000000007.

Example 1:

```Input: n = 2
Output: 1
Explanation: 1 is the 2nd number
of fibonacci series.
```

Example 2:

```Input: n = 5
Output: 5
Explanation: 5 is the 5th number
of fibonacci series.
```

You dont need to read input or print anything. Complete the function nthFibonacci() which takes n as input parameter and returns nth fibonacci number.

Expected Time Complexity: O(n)
Expected Auxiliary Space: O(n)

Constraints:
1<= n <=1000

Solution :

We know that this can be solved using recursion and dp but what about the matrix. Lets start with a matrix [[a,b],[c,d]] and in the left we have [ f(n) , f(n-1) ] and in the right we have [[a,b],[c,d]]  multiplied by [ f(n-1) , f(n-2) ]. We can find the value of a,b,c, and d by matching their coefficients. so now we can find the Fibonacci by just multiplying the matrix n times. Just like we make our own power function to reduce the time to calculate the power of big numbers we will here use exponentiation to calculate the power of a matrix.

const int mod = 1e9+7;
vector<vector<long long int>>st ={{1,1},{1,0}};

vector<vector<long long int>> multiply(vector<vector<long long int>>&a,vector<vector<long long int>>&b){
int n = a.size();
vector<vector<long long int>>ans(n,vector<long long int>(n,0LL));
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
for(int k=0; k<n; k++){
ans[i][j] += (a[i][k]*b[k][j])%mod;
}
ans[i][j]%=mod;
}
}
return ans;
}

vector<vector<long long int>> helper(vector<vector<long long int>>&a, int n){
if(n==0)return {{1,0},{0,1}};
if(n==1)return a;
vector<vector<long long int>> temp = helper(a,n/2);
vector<vector<long long int>> ans = multiply(temp,temp);
if(n&1) ans = multiply(ans,a);
return ans;
}

long long int nthFibonacci(long long int n){
vector<vector<long long int>>ans = helper(st,n);

return ans[0][1];
}