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, \dots, 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, \dots, n$ ，记 $G (n)$ 为所有构造在这些顶点上的美丽图的数目。已知 $G (3) = 24$ ， $G (4) = 186$ ， $G (15) = 12472315010483328$ 。

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