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)?919747298(mod1000000007).

Find g(10000)mod1000000007.

I've come up with a few ideas, and this is realistically the best idea that I have.

Every possible graph within the constraints are trees. And using this, I've been leaning towards generating all of the isomorphs for the number of nodes N and then using each isomorph and coloring it validly, hashing that coloring, and then collecting the total number of unique hashes.

Am I going in the correct direction? Is it simpler than this?

I feel like I'm missing a group or some sort of lemma that would make this problem at lot easier to approach. I've been thinking about this for days, and 50+ Wikipedia about astronomically specific types of graph coloring. I need another perspective. Cheers, /sci/