Count Ways to Reach the Nth Stair

Given a number of stairs, starting from the 0th stair, calculate the number of distinct ways you can reach the Nth stair. You can climb either one step or two steps at a time.

Input:

The first line contains an integer 'T', representing the number of test cases.
Each test case consists of a single integer 'N', which denotes the number of stairs.

Output:

For each test case, print the number of distinct ways to reach the Nth stair modulo 10^9+7.
Each output should be printed on a separate line.

Example:

Input:
N = 3

Explanation:
You can climb stairs in the following distinct ways:
1. One step at a time: (0, 1), (1, 2), (2, 3)
2. Two steps at first, then one step: (0, 2), (1, 3)
3. One step then two steps: (0, 1), (1, 3)

Constraints:

• 1 ≤ T ≤ 100
• 0 ≤ N ≤ 10¹⁸

Note:

No need to print outputs, it is handled by the system.