Problem 677

Coloured Graphs

Let $g (n)$ be the number of undirected graphs with $n$ nodes satisfying the following properties:

The graph is connected and has no cycles or multiple edges.
Each node is either red, blue, or yellow.
A red node may have no more than $4$ edges connected to it.
A blue or yellow node may have no more than $3$ edges connected to it.
An edge may not directly connect a yellow node to a yellow node.

For example, $g (2) = 5$ , $g (3) = 15$ , and $g (4) = 57$ .
You are also given that $g (10) = 710249$ and $g (100) \equiv 919747298 (\mod 1 000 000 007)$ .

Find $g (10 000) mod 1 000 000 007$ .

图染色

记 $g (n)$ 为有 $n$ 个结点并满足以下性质的无向图总数：

该图是连通图、无环、无重边。
每个结点被染上红色、蓝色或黄色之一。
每个红色结点至多与 $4$ 条边相连。
每个蓝色或黄色结点至多与 $3$ 条边相连。
黄色结点之间不能直接相连。

例如， $g (2) = 5$ ， $g (3) = 15$ ， $g (4) = 57$ 。
还已知 $g (10) = 710249$ ， $g (100) \equiv 919747298 (\mod 1 000 000 007)$ 。

求 $g (10 000) mod 1 000 000 007$ 。