A different way to get a result like this is to observe that the nth Fibonacci number is obtainable as the coefficient of x in x^n mod (x^2-x-1) via the usual matrix exponentiation argument, apply Kronecker substitution, and compute pow(b, n, b**2-b-1)//b.