Задача 324
Построение башен

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

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

Найдите f(1010000) mod 100000007.

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net