Problem 984
Knights and Horses
In Western chess, a knight is a piece that moves either two squares horizontally and one square vertically, or one square horizontally and two squares vertically, and is capable of jumping over any intervening pieces.
Chinese chess has a similar piece called the horse, whose moves have an identical displacement as a knight’s move; however, a horse, unlike a knight, is unable to jump over intervening pieces.
More specifically, a horse’s move consists of two steps: An orthogonal move of one square, followed by a diagonal move by one square in the same direction as the orthogonal move. If the orthogonal square is occupied by another piece, the horse is unable to move in that direction.
Specifically the horse in the centre of the above board can move to the squares $b_{11},b_{12},b_{21},b_{22},b_{31},b_{32},b_{41},b_{42}$ providing the squares $a_{1},a_{2},a_{3},a_{4}$ are unoccupied. For example, if $a_2$ was occupied then it could not move to $b_{21}$ or $b_{22}$.
A set of squares on a chessboard is called knight-connected if a knight can travel between any two squares in the set using only legal moves without using any squares not in the set. A set of squares on a chessboard is called horse-disjoint if, when a horse is placed on every square in the set (and no other square), no horse can attack any other.
Let $f(N)$ be the number of knight-connected, horse-disjoint non-empty subsets of an $N\times N$ chessboard. For example, $f(3) = 9$, consisting of the nine singleton sets. You are also given that $f(5) = 903, f(100) = 8658918531876$, and $f(10000) \equiv 377956308 \bmod 10^9+7$.
Find $f(10^{18})$. Give your answer modulo $10^9+7$.
骑士与马
在国际象棋中有一种走”日”字形的棋子叫做骑士，可以横向移动两格并纵向移动一格，或横向移动一格并纵向移动两格，并且可以跳过路径上的任何棋子。
在中国象棋中有一种类似的棋子叫做马，其移动路径与骑士相同，但与骑士不同的是，马不能任意跳过路径上的棋子。
具体来说，马的移动由两步组成：先沿直线方向移动一格，再沿同一方向的对角线移动一格。如果直线方向上的那一格被其它棋子占据，则马无法朝该方向移动。
如上图所示，棋盘中央的马可以移动到$b_{11},b_{12},b_{21},b_{22},b_{31},b_{32},b_{41},b_{42}$这些格子的前提是$a_{1},a_{2},a_{3},a_{4}$这些格子未被占据。例如，如果$a_2$被占据，则马不能移动到$b_{21}$或$b_{22}$。
如果一个棋盘格集合满足以下条件，则称其为骑士连通的：骑士可以从该集合的任意一个格子通过合法移动抵达任意另一个格子，且移动期间只落在该集合内的格子上；如果一个棋盘格集合满足以下条件，则称其为马不相攻的：当在该集合的每个格子上（且仅在这些格子上）各放置一只马时，没有任何一只马能够攻击到其它的马。
记$f(N)$为$N\times N$棋盘上所有既骑士连通又马不相攻的非空棋盘格子集的数目。例如，$f(3) = 9$，即九个棋盘格各自单独构成的集合。已知$f(5) = 903$，$f(100) = 8658918531876$，$f(10000) \equiv 377956308 \bmod 10^9+7$。
求$f(10^{18})$，并对$10^9+7$取余作为你的答案。