This riddle was proposed by Lorenzo Gianferrari Pini and Radu-Alexandru Todor - thanks!

Given a square binary matrix of order NN, A∈M(Z2)N×NA\in M(\mathbb{Z}_2)_{N\times N} such there is exactly one "1" value in each row and column of AA, we can find the lowest m>0m>0 such that Am=IA^m=I, the identity matrix.

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

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

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

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

Solvers