def power(a, n: int):
    """Return `a` to the n-th power, uses exponentiation by squaring i.e square and multiply
    """
    # Shortcuts are evaluated here to avoid code duplication

    if a == 0:
        if n > 0:
            return 0  # 0^n = 0 for n > 0

    if n == 0:
        return 1  # a^0 = 1 (0^0 = 1 is a convention in number theory)

    if n == 1:
        return a  # a^1 = a

    if a == 1:
        return a  # 1^n = 1, n integer

    def sqr_mul(x, e):
        if e == 1:
            return x
        elif e % 2 == 0:
            return sqr_mul(x * x, e // 2)
        elif e % 2 != 0 and e > 2:
            return x * sqr_mul(x * x, (e - 1) // 2)

    return sqr_mul(a, n)