Problems
Triomino
Triomino
In how many ways can you tile a \textbf{2 × n} rectangle with triominoes? A triomino is a geometric shape made from three squares joined along complete edges. There are only two possible triominoes:
\includegraphics{https://static.e-olymp.com/content/12/12088b401e5e009ceb3d1173a855103dff63b597.jpg}
For example, you can tile a \textbf{2 × 3} rectangle only in \textbf{3} different ways. As the answer can be quite big, you just need to find the number of ways modulo \textbf{10^6}.
\InputFile
The first line contains the number of test cases \textbf{t} (\textbf{1 ≤ t ≤ 100}). Each of the following \textbf{t} lines contains the value of \textbf{n} (\textbf{0 < n < 10^9}).
\OutputFile
For each test case print in a separate line a number of ways you can tile a \textbf{2 × n} rectangle. Print the answer modulo \textbf{10^6}.
Input example #1
3 3 4 6
Output example #1
3 0 11