# Nth Fibonacci Number

Prashant | Fri, 12 Jun, 2020 | 359

## Nth Fibonaci Number

Nth fibonacci number is a mostly asked in placements in many other competitive programming, So what is the best optimal solution ?

Don't worry just stay with us and learn with fun.

## Question :-

Given a positive integer N, find the Nth fibonacci number. Since the answer can be very large, print the answer modulo 1000000007.

Input:
The first line of input contains T denoting the number of testcases.Then each of the T lines contains a single positive integer N.

Output:
Output the Nth fibonacci number.

Constraints:
1 <= T <= 200
1 <= N <= 1000
Example:
Input:

3
1
2
5
Output:
1
1
5

## Best optimal solution :-

``````#include<bits/stdc++.h>
using namespace std;
int f[100000];
int fib(int n) {
f[0]=0;f[1] =1;
for(int i=2;i<=n; i++)
f[i]= (f[i-1]+f[i-2])%1000000007;  // to make it in form of Int
return f[n];
}
int main()
{
int t;
cin>>t;
while(t-->0){
int n;
cin>>n;
cout<<fib(n)<<endl;
}
return 0;
}``````