741 : グリッドの二色塗り分け

$n \times n$の正方グリッドを白か黒で塗り分ける。ただし、どの行もどの列も黒いセルをちょうど2つ含むようにする。このような塗り分けが何通りあるかを$f(n)$とする。 たとえば$f(4)=90, f(7)=3110940, f(8)=187530840$である。

$g(n)$を、塗り分け方法のうち、回転させたものや対称なものは同じもの1つとして数えたときの塗り分け方法とする。$g(4)=20, g(7)=390816, g(8)=23462347$なので、$g(7)+g(8)=23853163$である。

$g(7^7)+g(8^8)$を$1\,000\,000\,007$で割った余りを答えよ。