Detailed mathematical approach

Problem Summary

Let \(g(n)\) denote the number of distinct \(n\times n\) binary grids in which every row and every column contains exactly two black cells, where two grids are considered the same if one can be obtained from the other by a symmetry of the square.

Equivalently, we count orbits of \(n\times n\) \(0\)-\(1\) matrices with row sums and column sums equal to \(2\) under the dihedral group \(D_4\).

The required value is

$g(7^7)+g(8^8)\pmod{10^9+7}.$

Mathematical Approach

The solution never enumerates grids directly. It uses Burnside's lemma, then computes the number of colorings fixed by each symmetry type with short recurrences coming from generating functions.

Step 1: Burnside's Lemma Reduces the Orbit Count

There are eight symmetries of the square: the identity, one half-turn, two quarter-turns, two axial reflections, and two diagonal reflections. If we write

$I_n=\mathrm{Fix}(\text{identity}),\qquad T_n=\mathrm{Fix}(180^\circ),\qquad R_n=\mathrm{Fix}(90^\circ),$

$V_n=\mathrm{Fix}(\text{vertical reflection}),\qquad D_n=\mathrm{Fix}(\text{main diagonal reflection}),$

then the paired symmetries have equal fixed counts, so Burnside gives

$\boxed{g(n)=\frac{I_n+T_n+2R_n+2V_n+2D_n}{8}.}$

The whole problem is therefore reduced to evaluating five fixed-point formulas.

Step 2: Identity Symmetry Becomes a 2-Regular Bipartite Graph Count

For the identity symmetry, a grid is simply an \(n\times n\) binary matrix with row sum \(2\) and column sum \(2\). Interpreting rows and columns as the two parts of a bipartite graph, every valid grid corresponds to a simple \(2\)-regular bipartite graph on \(n+n\) labeled vertices.

Every connected component of such a graph is an alternating cycle of length \(2k\) with \(k\ge 2\). On chosen sets of \(k\) row labels and \(k\) column labels, the number of alternating cycles is \(k!^2/(2k)\), so the labeled-set construction yields the ordinary generating function

$U(x)=\sum_{n\ge 0} U_n x^n=\exp\left(\sum_{k\ge 2}\frac{x^k}{2k}\right)=e^{-x/2}(1-x)^{-1/2}.$

Differentiating gives

$\frac{U'(x)}{U(x)}=\frac{x}{2(1-x)},$

hence the coefficients satisfy

$\boxed{(n+1)U_{n+1}=nU_n+\frac{1}{2}U_{n-1}},\qquad U_0=1,\ U_1=0.$

The actual number of fixed grids is then

$\boxed{I_n=(n!)^2U_n.}$

Step 3: Diagonal Reflections Lead to Symmetric Components

A coloring fixed by a diagonal reflection corresponds to a symmetric \(0\)-\(1\) matrix with row sum \(2\). The connected components can be described on the label set \(\{1,\dots,n\}\):

ordinary cycles of length at least \(3\), and path components whose two endpoints carry diagonal entries, so each endpoint already contributes one black cell and the path supplies the second one. A path on \(k\) labeled vertices contributes \(k!/2\), while a cycle on \(k\) labeled vertices contributes \((k-1)!/2\).

Therefore

$S(x)=\sum_{n\ge 0} S_n x^n=\exp\left(\sum_{k\ge 2}\frac{x^k}{2}+\sum_{k\ge 3}\frac{x^k}{2k}\right).$

From the resulting differential equation one gets the recurrence

$\boxed{(n+1)S_{n+1}=2nS_n-(n-2)S_{n-1}-\frac{1}{2}S_{n-3}},$

with initial values

$S_0=1,\qquad S_1=0,\qquad S_2=\frac{1}{2},\qquad S_3=\frac{2}{3}.$

The diagonal fixed count is

$\boxed{D_n=n!S_n.}$

The other diagonal has the same count, so Burnside needs this term only once and doubles it.

Step 4: Half-Turn and Quarter-Turn Rotations Are Counted on Quotient Structures

For a half-turn, opposite rows and opposite columns are paired. When \(n=2m\) is even, the quotient has \(m\) row-pairs and \(m\) column-pairs. A connected component is either a doubled edge on one row-pair and one column-pair, or an alternating cycle on \(k\ge 2\) row-pairs and \(k\) column-pairs; each step has two local orientations, producing a factor \(4^k\).

This gives

$E(x)=\sum_{m\ge 0} E_m x^m=\exp\left(x+\sum_{k\ge 2}\frac{4^k x^k}{2k}\right)=e^{-x}(1-4x)^{-1/2},$

so

$\boxed{(m+1)E_{m+1}=(4m+1)E_m+4E_{m-1}},\qquad E_0=1,\ E_1=1,$

and the even half-turn count is

$\boxed{T_{2m}=(m!)^2E_m.}$

When \(n=2m+1\) is odd, there is also a central row and a central column, forcing one distinguished open chain in the quotient. If \(O_m\) counts that case, then adding one more paired row and one more paired column either extends the distinguished chain in \(4\) ways or creates a terminal attachment in \(2\) ways. Therefore

$\boxed{O_m=4O_{m-1}+2E_{m-1}},\qquad O_0=0,$

and

$\boxed{T_{2m+1}=(m!)^2O_m.}$

For a quarter-turn, no odd grid can be fixed, so only \(n=2m\) matters. After quotienting by the rotation, the connected pieces form a signed cycle class with a forbidden size-\(2\) component, which gives

$Q(x)=\sum_{m\ge 0} Q_m x^m=\exp\left(\sum_{k\ge 1}\frac{2^{k-1}x^k}{k}-\frac{x^2}{2}\right)=e^{-x^2/2}(1-2x)^{-1/2}.$

Hence

$\boxed{(m+1)Q_{m+1}=(2m+1)Q_m-Q_{m-1}+2Q_{m-2}},$

with

$Q_{-2}=0,\qquad Q_{-1}=0,\qquad Q_0=1,$

and the quarter-turn contribution is

$\boxed{R_{2m}=m!Q_m,\qquad R_{2m+1}=0.}$

Step 5: Axial Reflections Collapse to a Simple Closed Form

A vertical or horizontal reflection is possible only for even \(n=2m\). In each row, the two black cells must occupy a mirror pair of columns, so each row chooses one of the \(m\) column-pairs. Since every column must contain exactly two black cells, every column-pair must be chosen by exactly two rows.

That is exactly the number of ways to partition the \(2m\) rows into \(m\) unordered pairs and assign those pairs to the \(m\) column-pairs, namely

$\boxed{V_{2m}=\frac{(2m)!}{2^m},\qquad V_{2m+1}=0.}$

Worked Example: \(n=4\)

Here \(n=4=2\cdot 2\), so all five symmetry types contribute.

For the identity, the recurrence gives

$U_2=\frac{1}{4},\qquad U_3=\frac{1}{6},\qquad U_4=\frac{5}{32},$

hence

$I_4=(4!)^2\cdot \frac{5}{32}=90.$

For the diagonal reflection, the recurrence gives \(S_4=3/4\), so

$D_4=4!\cdot \frac{3}{4}=18.$

For the half-turn, \(E_2=9/2\), so

$T_4=(2!)^2\cdot \frac{9}{2}=18.$

For the quarter-turn, \(Q_2=1\), so

$R_4=2!\cdot 1=2.$

For axial reflections,

$V_4=\frac{4!}{2^2}=6.$

Burnside then gives

$g(4)=\frac{90+18+2\cdot 2+2\cdot 6+2\cdot 18}{8}=\frac{160}{8}=20,$

which matches the small check used by the implementation.

How the Code Works

The C++, Python, and Java implementations all follow the same pipeline. They first precompute modular inverses up to \(n+1\), because every recurrence divides by \(n+1\) or \(m+1\) inside arithmetic modulo \(10^9+7\).

Next they scan factorials to obtain \(n!\) and \(\lfloor n/2\rfloor!\). Then they evaluate the identity, diagonal, half-turn, and quarter-turn recurrences using constant-sized rolling state, and they compute the axial reflection term from the closed formula \((2m)!/2^m\).

Finally they assemble

$\frac{I_n+T_n+2R_n+2V_n+2D_n}{8}\pmod{10^9+7}$

by multiplying with the modular inverse of \(8\). No grid, graph, orbit table, or search tree is built explicitly; only the recurrence states and the inverse table are needed. The implementation evaluates \(g(7^7)\) and \(g(8^8)\) separately and adds them modulo \(10^9+7\).

Complexity Analysis

Each symmetry contribution is computed by a single linear pass up to \(n\) or \(\lfloor n/2\rfloor\). Therefore the total running time is \(O(n)\). The modular-inverse table has size \(O(n)\), while the recurrence states use only \(O(1)\) extra space, so the total memory usage is \(O(n)\).

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=741
2. Burnside's lemma: Wikipedia - Burnside's lemma
3. Dihedral group: Wikipedia - Dihedral group
4. Exponential generating function: Wikipedia - Exponential generating function
5. Regular bipartite graph: Wikipedia - Regular graph