Count Ways To Reach The N-th Stair Problem Statement

You are given a number of stairs, N. Starting at the 0th stair, you need to reach the Nth stair. Each time you can either climb one step or two steps. You have to return the number of distinct ways to climb from the 0th step to the Nth step.

Input:

The first line contains an integer 'T', representing the number of test cases. For each test case, there is a single integer 'N' denoting the number of stairs.

Output:

For each test case, print the number of distinct ways to climb to the top of the stairs. Since the result could be large, return it modulo 10^9+7. Output for each test case should be printed in a separate line.

Example:

Input:

N=3

Output:

3

Explanation:

There are three ways to climb to the third stair: (0, 1, 2, 3) by taking one step at a time, (0, 2, 3) by taking a two-step followed by a one-step, and (0, 1, 3) by taking a one-step followed by a two-step.

Constraints:

• 1 ≤ T ≤ 100
• 0 ≤ N ≤ 1018

Note:

You do not need to print anything. This has already been managed.