Məsələlər
Triomino
Triomino
2 x n ölçülü düzbucaqlını triominolarla neçə üsulla qapamaq mümkündür? Aşağıda təsvir olunmuş ilk iki həndəsi fiqur \textbf{triomino} adlanır (başqa cür triomino mövcud deyil) Göründüyü kimi, \textbf{triomino} - üç ədəd \textbf{1 x 1} ölçülü kvadratik tərəf birləşməsi ilə əmələ gəlir:
\includegraphics{https://static.e-olymp.com/content/12/12088b401e5e009ceb3d1173a855103dff63b597.jpg}
Məsələn, \textbf{2 × 3 ölçülü düzbucaqlını üç müxtəlif üsulla qapamaq olar (yuxarıda təsvir olunmuş son üç forma).}
Cavabın kifayət qədər böyük ola biləcəyini nəzərə alaraq, Siz üsullar sayının \textbf{10^6}-ya görə modulunu tapsanız kifayətdir.
\InputFile
Birinci sətirdə testlər sayını göstərən \textbf{T} (\textbf{1} ≤ \textbf{T} ≤ \textbf{100}) ədədi verilir. Sonrakı \textbf{T} sətirdə isə,\textbf{ n} (\textbf{0} < \textbf{n} < \textbf{10^9}) ədədinin müvafiq testə uyğun qiyməti sadalanır.
\OutputFile
\textbf{T} sətirdə, müvafiq test üçün \textbf{2 × n} ölçülü düzbucaqlını qapamaq üçün mümkün olan üsullar sayının \textbf{10^6}-ya görə modulu verilir.
Giriş verilənləri #1
3 3 4 6
Çıxış verilənləri #1
3 0 11