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 triomino adlanır (başqa cür triomino mövcud deyil) Göründüyü kimi, triomino - üç ədəd 1 x 1 ölçülü kvadratik tərəf birləşməsi ilə əmələ gəlir:
Məsələn, 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 10^6-ya görə modulunu tapsanız kifayətdir.
Giriş verilənləri
Birinci sətirdə testlər sayını göstərən T (1 ≤ T ≤ 100) ədədi verilir. Sonrakı T sətirdə isə, n (0 < n < 10^9) ədədinin müvafiq testə uyğun qiyməti sadalanır.
Çıxış verilənləri
T sətirdə, müvafiq test üçün 2 × n ölçülü düzbucaqlını qapamaq üçün mümkün olan üsullar sayının 10^6-ya görə modulu verilir.