Nth Fibonacci Number

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;
}