Huge Fibonacci modulo m optimization in Python 3
Fibonacci numbers grow exponentially. It means that the number of bits representing them grows linearly, and so does the complexity of computing nextFibonacci. It results in the overall quadratic complexity of your loop.

Good news is that you don't need to compute Fibonacci numbers at all. You only need to compute Pisano numbers. They obey the similar recurrence,

    p[n+1] = (p[n] + p[n-1]) % m


and by virtue of the modulo they never exceed m. A complexity of an individual addition stays constant, and the overall complexity becomes linear.

(Tiny additional: \$ (a + b)\ \textrm{mod}\ c\equiv a\ \textrm{mod}\ c\ + a\ \textrm{mod}\ c\$)