Ториангуляции

Для положительных вещественных чисел $a,b$ ,тор $a\times b$ это прямоугольник шириной $a$ и высотой $b,$ чьи левая и правая сторона идентичны, равно как и верхняя и нижняя сторона. Другими словами, при прочерчивании пути на прямоугольнике, достигнув края прямоугольника путь "оборачивается вокруг" и продолжается из соответствующей точки на противоположной стороне.

Выкладывание плиткой тора - это способ разбить его на равносторонние треугольники с длиной стороны 1. Например, следующие три изображения показывают соответственно тор $1\times \frac{\sqrt{3}}{2}$ с двумя треугольниками, тор $\sqrt{3}\times 1$ с четырьмя треугольниками и тор примерно $2.8432\times 2.1322$ с 14 треугольниками:

Для тора $a\times b$ два выкладывания плиткой называются эквивалентными, если возможно получить одно выкладывание из другого путем непрерывного перемещения всех треугольников так, чтобы ни в какой момент перемещения между ними не образовывалось пустот и никакие треугольники не перекрывались. Например, анимация ниже демонстрирует эквивалентность двух выкладываний:

Пусть $F\left(n\right)$ будет общим количеством неэквивалентных выкладываний плиткой для всех возможных торов с ровно $n$ треугольниками. Например, $F\left(6\right)=8$ с показанными ниже восемью неэквивалентными выкладываниями для торов с шестью треугольниками:

Пусть $G\left(N\right)=\sum _{n=1}^{N}F\left(N\right)$ . Известно, что $G\left(6\right)=14$ , $G\left(100\right)=8090$ и $G\left({10}^5\right)\equiv 645124048 (mod 1000000007)$

Найдите $G\left({10}^9\right)$ . В качестве ответа приведите остаток от деления полученного результата на $1000000007$ .

Решение