Binäre Gitterfärbung
Problem 741
Sei $f(n)$ die Anzahl der Möglichkeiten, wie ein quadratisches Gitter der Größe $n\times n$ gefärbt werden kann, wobei jede Gitterzelle entweder schwarz oder weiß ist, so dass jede Zeile und jede Spalte genau zwei schwarze Zellen enthält. Zum Beispiel ist $f(4) = 90$, $f(7) = 3110940$ und $f(8) = 187530840.$
Sei $g(n)$ die Anzahl der Einfärbungen in $f(n)$, die bis zu Rotationen und Reflexionen eindeutig sind. Es gilt $g(4) = 20$, $g(7) = 390816$ und $g(8) = 23462347$, was $g(7) + g(8) = 23853163$ ergibt.
Finden Sie $g(7 ^ 7) + g(8 ^ 8).$ Geben Sie Ihre Antwort modulo $1\,000\,000\,007.$