Ponder This Challenge - May 2026 - The Powers of a Binary Matrix

Given a square binary matrix of order $N$, $A\in M(\mathbb{Z}_2)_{N\times N}$ such that the sum of each row and column of $A$ is 1, we can find the lowest $m>0$ such that $A^m=I$, the identity matrix.

Denote by $g(N)$ the maximum such $m$ when going over all the matrices in $M(\mathbb{Z}_2)_{N\times N}$ satisfying the above condition.

For example, $g(10)=30$ and $g(50) = 180180$.

Your goal: Find $g(10^6)\ \text{mod}\ (10^9+7)$.

A bonus "*" will be given for finding $g(10^8)\ \text{mod}\ (10^9+7)$.