Ways to Reach Nth Stair

Given the number of stairs, initially at the 0th stair, you need to reach the Nth stair. Each time, you can either climb one step or two steps. Determine 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. The following lines contain an integer 'N' for each test case, representing the number of stairs.

Output:

For each test case, output the number of distinct ways to reach the top of the stairs, modulo 10^9+7. Output should be on a separate line for each test case.

Example:

Input:

N=3

Output:

3

Explanation:

Different ways to climb to the 3rd stair:

• Step by step: {0, 1, 2, 3}
• Two steps then one: {0, 2, 3}
• One step then two steps: {0, 1, 3}

Constraints:

• 1 <= T <= 100
• 0 <= N <= 10^18

Note:

You do not need to print anything; only implement the respective function and return the results.