e-olymp

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:

prb236

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 106-ya görə modulunu tapsanız kifayətdir.

Giriş verilənləri

Birinci sətirdə testlər sayını göstərən T (1T100) ədədi verilir. Sonrakı T sətirdə isə, n (0 < n < 109) ə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 106-ya görə modulu verilir.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri
3
3
4
6
Çıxış verilənləri
3
0
11