One-Dimensional Tile Combiner

An artist is designing a one-dimensional work of art by combining three types of rectangular tiles of sizes \(1\times1\), \(1\times2\), and \(1\times3\). The artist wants to know in how many different ways a row of length \(N\) can be completely covered using any combination of these tiles. Note that the order of the tiles matters.

Let \(dp[n]\) represent the number of ways to cover a row of length \(n\). The recurrence is given by:

[ dp[n] = dp[n-1] + dp[n-2] + dp[n-3], \quad \text{for } n \ge 1 ]

with the following base cases:

[ dp[0] = 1,\quad dp[1] = 1,\quad dp[2] = 2,\quad dp[3] = 4. ]

Use modulo \(10^9+7\) to keep the numbers within manageable limits.

inputFormat

The first line contains an integer \(T\) denoting the number of test cases. Each of the following \(T\) lines contains a single integer \(N\), the length of the row to be tiled.

Input is read from standard input (stdin).

outputFormat

For each test case, output a single line containing the number of unique ways to tile a row of length \(N\) modulo \(10^9+7\), written to standard output (stdout).

## sample

1
3

4

</p>