Yenidən hesablamaq?

Verilmiş tam n üçün 3 × 1 plitələrlə 4 × n ölçüsündə bir düzbucaqlını neçə fərqli üsulla bölmək mümkün olduğunu hesablayın.

Cavab çox böyük ola biləcəyi üçün nəticəni 1000000007-ə bölünərək qalıq kimi təqdim edin.

Giriş məlumatları

Birinci sətir testlərin sayını göstərən t (1 ≤ t ≤ 100) tam ədədini ehtiva edir. Hər bir test üçün bir tam ədəd n (1 ≤ n ≤ 10000) verilir.

Çıxış məlumatları

Hər bir test üçün cavabı ayrıca sətirdə 1000000007 modulu ilə çıxarın.