Problem 857

Beautiful Graphs

A graph is made up of vertices and coloured edges. Between every two distinct vertices there must be exactly one of the following:

A red directed edge one way, and a blue directed edge the other way
A green undirected edge
A brown undirected edge

Such a graph is called beautiful if

A cycle of edges contains a red edge if and only if it also contains a blue edge
No triangle of edges is made up of entirely green or entirely brown edges

Below are four distinct examples of beautiful graphs on three vertices:

Below are four examples of graphs that are not beautiful:

Let $G(n)$ be the number of beautiful graphs on the labelled vertices: $1,2,\ldots,n$. You are given $G(3)=24$, $G(4)=186$ and $G(15)=12472315010483328$.

Find $G(10^7)$. Give your answer modulo $10^9+7$.

美丽图

考虑由顶点和染色的边构成的图，任意两个顶点间必由以下三种情况之一相连：

一条红色的有向边和一条蓝色的有向边，两者方向相反
一条绿色的无向边
一条棕色的无向边

若进一步满足以下条件，则称之为美丽图：

任意环包含红色边当且仅当它也包含蓝色边
不存在仅由绿色边或仅由棕色边构成的三角形

如下所示的四张图均为包含三个顶点的美丽图：

如下所示的四张图均不是美丽图：

将顶点依次编号为$1,2,\ldots,n$，记$G(n)$为所有构造在这些顶点上的美丽图的数目。已知$G(3)=24$，$G(4)=186$，$G(15)=12472315010483328$。

求$G(10^7)$，并对$10^9+7$取余作为你的答案。