Пусть f(n) - число способов, которыми можно заполнить башню 3×3×n используя блоки 2×1×1.
Разрешено поворачивать блоки любыми способами, однако повороты, отражения и т.п. самой башни считаются различными башнями.

Например, при q = 100000007:
f(2) = 229,
f(4) = 117805,
f(10) mod q = 96149360,
f(10³) mod q = 24806056,
f(10⁶) mod q = 30808124.

Найдите f(10¹⁰⁰⁰⁰) mod 100000007.