<gh_stars>0
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# Fast Exponentiation
# <NAME> et <NAME> and <NAME> - 2014-2018


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


# snip{
def fast_exponentiation(a, b, q):
    """Compute (a pow b) % q, alternative shorter implementation

    :param int a b: non negative
    :param int q: positive
    :complexity: O(log b)
    """
    assert a >= 0 and b >= 0 and q >= 1
    result = 1
    while b:
        if b % 2 == 1:
            result = (result * a) % q
        a = (a * a) % q
        b >>= 1
    return result
# snip}

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# Fast Exponentiation
# <NAME> et <NAME> and <NAME> - 2014-2018


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


# snip{
def fast_exponentiation(a, b, q):
    """Compute (a pow b) % q, alternative shorter implementation

    :param int a b: non negative
    :param int q: positive
    :complexity: O(log b)
    """
    assert a >= 0 and b >= 0 and q >= 1
    result = 1
    while b:
        if b % 2 == 1:
            result = (result * a) % q
        a = (a * a) % q
        b >>= 1
    return result
# snip}
#!/usr/bin/env python3 # -*- coding: utf-8 -*- # Fast Exponentiation # <NAME> et <NAME> and <NAME> - 2014-2018 Compute (a pow b) % q      :param int a b: non negative     :param int q: positive     :complexity: O(log b) # only for documentation # 2 ** p # a ** (2 ** p) # b's binary decomposition contains 2 ** p # snip{ Compute (a pow b) % q, alternative shorter implementation      :param int a b: non negative     :param int q: positive     :complexity: O(log b) # snip}