Задача 554
Кентавры на шахматной доске

Кентавр может перемещаться по шахматной доске как король или конь. Рисунок ниже показывает разрешенные ходы кентавра (обозначенного перевернутым символом короля) на доске 8x8:

p554-centaurs.png

Можно показать, что на доске размером 2n×2n можно расположить не больше n2 ненаходящихся под боем друг друга кентавров.
Пусть C(n) будет количеством способов расположения n2 кентавров на доске размером 2n×2n так, чтобы ни один кентавр не находится под боем любого другого.
Например, C(1) = 4, C(2) = 25, C(10) = 1477721.

Пусть Fi будет i-тым числом Фибоначчи, определенным как F1 = F2 = 1 и Fi = Fi-1 + Fi-2 для i > 2.

Найдите $\displaystyle \left( \sum_{i=2}^{90} C(F_i) \right) \text{mod } (10^8+7)$.

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