Problem 554
Centaurs on a chess board
On a chess board, a centaur moves like a king or a knight. The diagram below shows the valid moves of a centaur (represented by an inverted king) on an 8x8 board.
It can be shown that at most n2 non-attacking centaurs can be placed on a board of size 2n×2n.
Let C(n) be the number of ways to place n2 centaurs on a 2n×2n board so that no centaur attacks another directly.
For example C(1) = 4, C(2) = 25, C(10) = 1477721.
Let Fi be the ith Fibonacci number defined as F1 = F2 = 1 and Fi = Fi-1 + Fi-2 for i > 2.
Find $\displaystyle \left( \sum_{i=2}^{90} C(F_i) \right) \text{mod } (10^8+7)$.
棋盘上的半人马
在国际象棋棋盘上，半人马可以像国王或者骑士那样移动。如下的图象说明了半人马（用颠倒的国王表示）在8x8的棋盘上的有效移动范围。
可以证明，在一个2nx2n的棋盘上，最多可以放置n2个互不攻击的半人马。
记C(n)为在2nx2n的的棋盘上放置n2个互不攻击的半人马的方式数。
例如，C(1) = 4，C(2) = 25，C(10) = 1477721。
记Fi为第i个斐波那契数，斐波那契数的定义为F1 = F2 = 1且当i > 2时Fi = Fi-1 + Fi-2。
求$\displaystyle \left( \sum_{i=2}^{90} C(F_i) \right) \text{mod } (10^8+7)$。