Problem 741

Binary grid colouring

Let $f(n)$ be the number of ways an $n\times n$ square grid can be coloured, each cell either black or white, such that each row and each column contains exactly two black cells.
For example, $f(4)=90$, $f(7) = 3110940$ and $f(8) = 187530840$.

Let $g(n)$ be the number of colourings in $f(n)$ that are unique up to rotations and reflections.
You are given $g(4)=20$, $g(7) = 390816$ and $g(8) = 23462347$ giving $g(7)+g(8) = 23853163$.

Find $g(7^7) + g(8^8)$. Give your answer modulo $1\ 000\ 000\ 007$.

网格黑白染色

对$n\times n$的网格进行黑白染色，记使得每行和每列都恰好有两个黑格的染色方法数目为$f(n)$。
例如，$f(4)=90$，$f(7) = 3110940$，$f(8) = 187530840$。

在$f(n)$中，将所有旋转或翻转后可重合的染色方法视为相同的方法，记不同染色方法数目为$g(n)$。
已知$g(4)=20$，$g(7) = 390816$，$g(8) = 23462347$，因此$g(7)+g(8) = 23853163$。

求$g(7^7) + g(8^8)$，并将你的答案对$1\ 000\ 000\ 007$取余。