Fibonacci modulo m

fibmodm.py

def _fibonacci(n, modulo):
    if n == 0:
        return (0, 1)
    # get F(n/2) and F(n/2+1)
    a, b = _fibonacci(n//2, modulo)

    # F(n/2 + 1)*2 - F(n/2) might be negative because of the modulo
    t = b*2 - a
    if t < 0:
        t += modulo
    c = a * t

    d = a ** 2 + b ** 2

    c %= modulo
    d %= modulo
    
    # return F(n) and F(n+1)
    if n % 2:
        return (d, c+d)
    return (c, d)

def fibonacci(n, modulo):
    # _fibonacci returns F(n) and F(n+1)
    return _fibonacci(n, modulo)[0]

if __name__ == "__main__":
    print("F(5):", fibonacci(5, 1000))
    print("F(5) modulo 10:", fibonacci(5, 10))
    print("F(1000000) modulo 12345:", fibonacci(1000000, 12345))