Problem 670

Colouring a Strip

A certain type of tile comes in three different sizes - $1\times 1$, $1\times2$, and $1\times 3$ - and in four different colours: blue, green, red and yellow. There is an unlimited number of tiles available in each combination of size and colour.

These are used to tile a $2\times n$ rectangle, where $n$ is a positive integer, subject to the following conditions:

The rectangle must be fully covered by non-overlapping tiles.
It is not permitted for four tiles to have their corners meeting at a single point.
Adjacent tiles must be of different colours.

For example, the following is an acceptable tiling of a $2\times 12$ rectangle:

but the following is not an acceptable tiling, because it violates the “no four corners meeting at a point” rule:

Let $F(n)$ be the number of ways the $2\times n$ rectangle can be tiled subject to these rules. Where reflecting horizontally or vertically would give a different tiling, these tilings are to be counted separately.

For example, $F(2) = 120$, $F(5) = 45876$, and $F(100)\equiv 53275818 \pmod{1\ 000\ 004\ 321}$.

Find $F(10^{16}) \bmod 1\ 000\ 004\ 321$.

彩砖条形铺盖

某种砖块有三种不同的大小，分别是$1\times 1$、$1\times2$和$1\times 3$，同时又有四种不同的颜色：蓝色、绿色、红色和黄色。每种大小和颜色组合的砖块都不限量供应。

这些砖块被用于铺盖大小为$2\times n$的长方形，其中$n$为正整数。铺盖过程必须满足以下条件：

长方形必须完全被覆盖，且砖块之间不能重叠。
不允许有四块砖块共用一个顶点。
相邻的砖块必须有不同的颜色。

例如，下图是对大小为$2\times 12$的长方形的一种合理铺盖：

而下图则是一种不合理铺盖，因为这种铺盖违背了“四块砖块不允许共用一个顶点”的规则：

记$F(n)$为大小为$2\times n$的长方形上的合理铺盖总数。上下或左右镜像对称的铺盖视为不同的铺盖。

已知，$F(2) = 120$，$F(5) = 45876$，$F(100)\equiv 53275818 \pmod{1\ 000\ 004\ 321}$。

求$F(10^{16}) \bmod 1\ 000\ 004\ 321$。