Для положительных вещественных чисел $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(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$.