Problem 780

Toriangulations

For positive real numbers $a,b$, an $a\times b$ torus is a rectangle of width $a$ and height $b$, with left and right sides identified, as well as top and bottom sides identified. In other words, when tracing a path on the rectangle, reaching an edge results in “wrapping round” to the corresponding point on the opposite edge.

A tiling of a torus is a way to dissect it into equilateral triangles of edge length $1$. For example, the following three diagrams illustrate respectively a $1\times \frac{\sqrt{3}}{2}$ torus with two triangles, a $\sqrt{3}\times 1$ torus with four triangles, and an approximately $2.8432\times 2.1322$ torus with fourteen triangles:

Two tilings of an $a\times b$ torus are called equivalent if it is possible to obtain one from the other by continuously moving all triangles so that no gaps appear and no triangles overlap at any stage during the movement. For example, the animation below shows an equivalence between two tilings:

Let $F(n)$ be the total number of non-equivalent tilings of all possible tori with exactly $n$ triangles. For example, $F(6)=8$, with the eight non-equivalent tilings with six triangles listed below:

Let $G(N)=\sum_{n=1}^N F(n)$. You are given that $G(6)=14$, $G(100)=8090$, and $G(10^5)\equiv 645124048 \pmod{1\ 000\ 000\ 007}$.

Find $G(10^9)$. Give your answer modulo $1\ 000\ 000\ 007$.

环面三角形平铺

对于正实数$a$和$b$，一个$a\times b$环面是将一个宽为$a$、高为$b$的长方形的左右两边和上下两边分别接合构成的图形。换言之，如果在这个长方形上移动，每当碰到一条边时，就会“穿越”到其相对边的同一位置。

环面上的一种平铺是指将换面分割为边长为$1$的等边三角形的一种方式。例如，下面三张图分别展示了一个$1\times \frac{\sqrt{3}}{2}$环面用两个三角形平铺，一个$\sqrt{3}\times 1$环面用四个三角形平铺，和一个约$2.8432\times 2.1322$环面用十四个三角形平铺：

在$a\times b$环面上，如果两种平铺可以通过连续、不留空隙、不相互覆盖地移动所有三角形相互转化，则认为这两种平铺是等价的。例如，如下动画展示了如何将一种平铺转化为等价的另一种平铺：

记$F(n)$为所有使用$n$个三角形且互不等价的平铺的数量。例如，$F(6)=8$，而这八种使用了六个三角形且互不等价的平铺如下图所示：

记$G(N)=\sum_{n=1}^N F(n)$。已知$G(6)=14$，$G(100)=8090$，$G(10^5)\equiv 645124048 \pmod{1\ 000\ 000\ 007}$。

求$G(10^9)$，并将你的答案对$1\ 000\ 000\ 007$取余。