If we calculate $a^2 \bmod 6$ for $0 \leq a \leq 5$ we get: $0,1,4,3,4,1$.

The largest value of $a$ such that $a^2 \equiv a \bmod 6$ is $4$.
Let's call $M(n)$ the largest value of $a \lt n$ such that $a^2 \equiv a \pmod n$.
So $M(6) = 4$.

Find $\sum M(n)$ for $1 \leq n \leq 10^7$.