在西方国际象棋中，马是一个可以水平移动两个方格和垂直移动一个方格，或者水平移动一个方格和垂直移动两个方格的棋子，并且能够跳过任何中间的棋子。

中国象棋有一个类似的棋子，称为马，其走法与马的走法具有相同的位移；然而，与骑士不同，马无法跳过中间的棋子。

更具体地说，马的移动由两个步骤组成：正交移动一格，然后是与正交移动相同方向的对角线移动一格。如果正交格子被另一块棋子占据，马就无法朝该方向移动。 具体来说，如果方格 $a_1,a_2,a_3,a_4$ 未被占用，则上图板中心的马可以移动到方格 $b_{11},b_{12},b_{21},b_{22},b_{31},b_{32},b_{41},b_{42}$ 。例如，如果$a_2$被占用，则它无法移动到$b_{21}$或$b_{22}$。

棋盘上的一组方格被称为骑士连接，如果一个马可以仅使用合法的移动在该组中的任意两个方格之间移动，而不使用该组中的任何方格。 棋盘上的一组方格被称为马不相交，如果当一匹马被放置在该组中的每个方格（并且没有其他方格）上时，没有一匹马可以攻击任何其他方格。 令 $f(N)$ 为 $N\times N$ 棋盘的马相连、马不相交的非空子集的数量。例如，$f(3)=9$，由九个单例集组成。您还可以得到 $f(5)=903,f(100)=8658918531876$ 和 $f(10000)\equiv 377956308mod{10}^9+7$。

求$f({10}^{18})$。以 ${10}^9+7$ 为模给出你的答案。