Taco's Staircase Problem

Sam wants to climb a staircase with N steps. At each move, he can take 1, 2, or 3 steps. Your task is to determine the number of distinct ways that Sam can reach the top of the staircase. Because the answer can be very large, you must return the result modulo 10⁹+7.

The relation used to compute the number of ways is given by the recurrence:

\( dp[n] = dp[n-1] + dp[n-2] + dp[n-3] \) for \( n \ge 3 \),

with the initial conditions:

\( dp[0] = 1 \), \( dp[1] = 1 \), and \( dp[2] = 2 \).

Complete the solution by reading the test cases from stdin and writing the results to stdout.

inputFormat

The input begins with an integer T representing the number of test cases. Each of the following T lines contains a single integer N, indicating the number of steps in the staircase.

outputFormat

For each test case, output a single integer: the number of distinct ways to reach the top of the staircase modulo 10⁹+7. Each result should be printed on a new line.

## sample

3
3 4 7

4
7
44

</p>