def fast_exponentiation2(a, b, q):
    """Compute (a pow b) % q

    :param int a b: non negative
    :param int q: positive
    :complexity: O(log b)
    """
    assert a >= 0 and b >= 0 and q >= 1
    p = 0               # only for documentation
    p2 = 1              # 2 ** p
    ap2 = a % q         # a ** (2 ** p)
    result = 1
    while b > 0:
        if p2 & b > 0:  # b's binary decomposition contains 2 ** p
            b -= p2
            result = (result * ap2) % q
        p += 1
        p2 *= 2
        ap2 = (ap2 * ap2) % q
    return result
Compute (a pow b) % q

    :param int a b: non negative
    :param int q: positive
    :complexity: O(log b)