Count Number Of Ways To Cover A Distance

Divyansh is in Dhanbad and wants to travel to different places. He can take one, two or three steps at max while travelling. He knows the distance and wants to find the number of ways to reach his destination. He is weak at calculations and wants your help in this. Given the distance from Dhanbad to his destination, count the total number of ways to cover the distance with 1, 2 and 3 steps.

Input Format:

The first line of input contains an integer ‘T’ denoting the number of test cases.

The next ‘T’ lines represent the ‘T’ test cases.

The first and the only line of each test case contains an integer ‘N’ denoting the distance between Dhanbad and the destination.

Output Format:-

For each test case, print an integer denoting the number of ways to cover the distance. 

Print the answer mod 10^9+7.

Note :

You don’t have to print anything, it has already been taken care of. Just implement the given function.

Follow Up:

Can you solve this using only O(1) space?

Constraints:

1 <= T <= 50
1 <= N <= 10^4

Time Limit: 1 sec

Sample Input 1:

2
3 
4

Sample Output 1:

4
7

Explanation of the Sample Input 1:

Test case 1:

Below are the four ways
1 step + 1 step + 1 step
1 step + 2 step
2 step + 1 step
3 step

Test case 2:

Below are the seven ways
1 step + 1 step + 1 step + 1 step
1 step + 2 step + 1 step
2 step + 1 step + 1 step 
1 step + 1 step + 2 step
2 step + 2 step
3 step + 1 step
1 step + 3 step

Sample Input 2:

2
1
2

Sample Output 2:

1
2

Explanation of the Sample Input 2:

Test case 1:
Below is the only way
1 step

Test case 2:
Below are the three ways
1step + 1 step
2 step