def mod_rec_exponentiate(number, exponent, mod):
    """
    Modular exponentiation - recursive method
    Complexity: O(logEXPONENT)

    Sometimes, when the number can be extremely big, we find
    the answer modulo some other number. We can do it in both
    the recursive and the serial way. For simplicity we just
    implement it in the recursive method.
    """
    if exponent == 0:
        return 1
    elif exponent % 2 == 0:
        return mod_rec_exponentiate((number**2) % mod, exponent//2, mod)
    else:
        return number * mod_rec_exponentiate((number**2) % mod, exponent//2, mod) % mod