# N-th Fibonacci Number

Last Updated: 5 Feb, 2021
Difficulty: Moderate

## PROBLEM STATEMENT

#### Since the answer can be very large, return the answer modulo 10^9 +7.

##### Fibonacci number is calculated using the following formula:
F(n) = F(n-1) + F(n-2),
Where, F(1) = F(2) = 1.
##### For Example:
For ‘N’ = 5, the output will be 5.
##### Input Format:
The first line contains a single integer ‘T’ denoting the number of test cases to be run. Then the test cases follow.

The first line of each test case contains a single integer ‘N’, representing the integer for which we have to find its equivalent Fibonacci number.
##### Output Format:
For each test case, print a single integer representing the N’th Fibonacci number.

Return answer modulo 10^9 + 7.

Output for each test case will be printed in a separate line.
##### Note:
You are not required to print anything; it has already been taken care of. Just implement the function.
##### Constraints:
1 <= T <= 10
1 <= N <= 10^5

Time Limit: 1 sec.
Can you solve it in Time Complexity better than O(N)?

## Approach 1

• In this approach, we use recursion and uses a basic condition that :
• If ‘N’ is smaller than ‘1’(N<=1) we return ‘N’
• Else we call the function again as ninjaJasoos(N-1) + ninjaJasoos(N-2).
• In this way, we reached our answer.