Граф состоит из вершин и цветных ребер. Между любыми двумя его вершинами должно находиться ровно одно из следующих:

• Красное ориентированное ребро в одном направлении и синее ориентированное ребро в обратном направлении
• Зеленое неориентированное ребро
• Коричневое неориентированное ребро

• Цикл ребер содержит красное ребро тогда и только тогда, когда он также содержит синее ребро
• Ни один образованный ребрами треугольник не состоит из исключительно зеленых или исключительно коричневых ребер

Ниже приведены четыре различных примера прекрасных графов с тремя ребрами:

Ниже приведены четыре различных примера графов, которые не являются прекрасными:

Пусть $G(n)$ будет количеством прекрасных графов, состоящих из вершин, пронумерованных $1,2,\ldots,n$. Известно, что $G(3)=24$, $G(4)=186$ и $G(15)=12472315010483328$.

Найдите $G(10^7)$. В качестве ответа приведите остаток от деления полученного числа на $10^9+7$.