Задача 677
Разноцветные графы

Пусть $g(n)$ будет количеством неориентированных графов с $n$ вершинами, имеющих следующие свойства:

  • Граф является связным и не содержит циклы или кратные ребра.
  • Каждая вершина окрашена в красный, синий или желтый цвет.
  • Красная вершина может иметь не более 4 соединенных с ней ребер.
  • Синяя или желтая вершина может иметь не более 3 соединенных с ней ребер.
  • Ребро не может непосредственно соединять желтую вершину с желтой вершиной.

Например, $g(2)=5$, $g(3)=15$ и $g(4) = 57$.
Также известно, что $g(10) = 710249$ и $g(100) \equiv 919747298 \pmod{1\,000\,000\,007}$.

Найдите $g(10\,000) \bmod 1\,000\,000\,007$.

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net