Binäre Gitterfärbung

Problem 741

Sei f(n) die Anzahl der Möglichkeiten, wie ein quadratisches Gitter der Größe n×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(77)+g(88). Geben Sie Ihre Antwort modulo 1000000007.