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
    p2 = 1
    ap2 = a % q
    result = 1
    while b > 0:
        if p2 & b > 0:
            b -= p2
            result = result * ap2 % q
        p += 1
        p2 *= 2
        ap2 = ap2 * ap2 % q
    return result
