Math and Number Theory

from math import gcd, lcm       # lcm is Python 3.9+

def gcd_iter(a, b):
    while b:
        a, b = b, a % b
    return abs(a)

def lcm_safe(a, b):
    """Divide FIRST to avoid overflow in fixed-width languages."""
    return 0 if a == 0 or b == 0 else abs(a // gcd(a, b) * b)

def ext_gcd(a, b):
    """Returns (g, x, y) with a*x + b*y = g = gcd(a, b)."""
    if b == 0:
        return a, 1, 0
    g, x1, y1 = ext_gcd(b, a % b)
    return g, y1, x1 - (a // b) * y1

def mod_inverse(a, m):
    """Inverse of a mod m for any coprime m. None if not invertible."""
    g, x, _ = ext_gcd(a % m, m)
    return None if g != 1 else x % m

MOD = 10 ** 9 + 7

(a + b) % MOD
(a - b) % MOD                       # Python keeps this non-negative
(a * b) % MOD
pow(a, e, MOD)                      # fast modular exponentiation, O(log e)
pow(a, MOD - 2, MOD)                # modular inverse, prime MOD (Fermat)
(a * pow(b, MOD - 2, MOD)) % MOD    # a / b mod a prime MOD

def mod_pow(base, exp, mod):
    """Square and multiply, written out."""
    result = 1
    base %= mod
    while exp > 0:
        if exp & 1:
            result = result * base % mod
        base = base * base % mod
        exp >>= 1
    return result

// Java: normalize subtraction, and use long for every multiplication
long sub = ((a - b) % MOD + MOD) % MOD;
long mul = a % MOD * (b % MOD) % MOD;      // int * int overflows, cast to long
long inv = BigInteger.valueOf(a)
    .modInverse(BigInteger.valueOf(MOD)).longValue();

def is_prime(n):
    """Trial division by 6k ± 1. O(sqrt n)."""
    if n < 2:
        return False
    if n < 4:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True

def sieve(n):
    """All primes up to n. O(n log log n)."""
    if n < 2:
        return []
    flags = bytearray([1]) * (n + 1)
    flags[0] = flags[1] = 0
    for i in range(2, int(n ** 0.5) + 1):
        if flags[i]:
            flags[i * i::i] = bytearray(len(flags[i * i::i]))
    return [i for i in range(n + 1) if flags[i]]

def linear_sieve(n):
    """Smallest prime factor for every value up to n. O(n).
    Gives O(log n) factorization afterwards."""
    spf = list(range(n + 1))
    primes = []
    for i in range(2, n + 1):
        if spf[i] == i:
            primes.append(i)
        for p in primes:
            if p > spf[i] or i * p > n:
                break
            spf[i * p] = p
    return spf, primes

def factorize(n):
    """Prime factorization as {prime: exponent}. O(sqrt n)."""
    out = {}
    d = 2
    while d * d <= n:
        while n % d == 0:
            out[d] = out.get(d, 0) + 1
            n //= d
        d += 1 if d == 2 else 2        # skip evens after 2
    if n > 1:
        out[n] = out.get(n, 0) + 1
    return out

def factorize_with_spf(n, spf):
    """O(log n) once a linear sieve is built."""
    out = {}
    while n > 1:
        p = spf[n]
        while n % p == 0:
            out[p] = out.get(p, 0) + 1
            n //= p
    return out

def divisors(n):
    """All divisors, sorted. O(sqrt n)."""
    small, large = [], []
    i = 1
    while i * i <= n:
        if n % i == 0:
            small.append(i)
            if i != n // i:
                large.append(n // i)
        i += 1
    return small + large[::-1]

def euler_phi(n):
    """Count of integers in [1, n] coprime to n."""
    result = n
    p = 2
    while p * p <= n:
        if n % p == 0:
            while n % p == 0:
                n //= p
            result -= result // p
        p += 1
    if n > 1:
        result -= result // n
    return result

from math import comb, perm, factorial

comb(n, k)          # C(n, k), exact for any size in Python
perm(n, k)          # n! / (n-k)!
factorial(n)

MOD = 10 ** 9 + 7

class Binomial:
    """Precompute factorials for O(1) C(n, k) mod a prime."""
    def __init__(self, n, mod=MOD):
        self.mod = mod
        self.fact = [1] * (n + 1)
        for i in range(1, n + 1):
            self.fact[i] = self.fact[i - 1] * i % mod
        self.inv_fact = [1] * (n + 1)
        self.inv_fact[n] = pow(self.fact[n], mod - 2, mod)
        for i in range(n, 0, -1):
            self.inv_fact[i - 1] = self.inv_fact[i] * i % mod

    def C(self, n, k):
        if k < 0 or k > n:
            return 0
        return (self.fact[n] * self.inv_fact[k] % self.mod
                * self.inv_fact[n - k] % self.mod)

def pascal_row(n):
    """Row n of Pascal's triangle, O(n) with no division."""
    row = [1]
    for k in range(n):
        row.append(row[-1] * (n - k) // (k + 1))
    return row

def catalan(n):
    """C(2n, n) / (n + 1). Counts balanced parentheses, BST shapes,
    triangulations, and monotone lattice paths below the diagonal."""
    return comb(2 * n, n) // (n + 1)

bin(255), oct(255), hex(255)     # '0b11111111', '0o377', '0xff'
int("ff", 16)                    # 255
int("1010", 2)                   # 10
format(255, "b")                 # '11111111', no prefix
format(255, "08b")               # zero-padded

def to_base(n, base):
    """n >= 0, base 2..36."""
    if n == 0:
        return "0"
    digits = "0123456789abcdefghijklmnopqrstuvwxyz"
    out = []
    while n:
        n, r = divmod(n, base)
        out.append(digits[r])
    return "".join(reversed(out))

def digit_sum(n):
    total = 0
    while n:
        n, r = divmod(n, 10)
        total += r
    return total

def digit_count(n):
    """Number of decimal digits without string conversion."""
    import math
    return 1 if n == 0 else math.floor(math.log10(abs(n))) + 1

def reverse_number(n):
    """Guard 32-bit overflow before the last multiplication."""
    sign = -1 if n < 0 else 1
    n, out = abs(n), 0
    while n:
        n, d = divmod(n, 10)
        if out > (2 ** 31 - 1 - d) // 10:
            return 0                    # would overflow
        out = out * 10 + d
    return sign * out

# Python floors, C/C++/Java truncate toward zero
-7 // 2          # -4 in Python
# -7 / 2 is -3 in C, C++, and Java

# ceiling division, integer only, positive operands
(a + b - 1) // b
-(-a // b)                     # works for negatives in Python too

# integer square root, exact, no float error
import math
math.isqrt(n)                  # floor(sqrt(n)), never off by one

def is_perfect_square(n):
    if n < 0:
        return False
    r = math.isqrt(n)
    return r * r == n

# overflow-safe midpoint
mid = lo + (hi - lo) // 2

# Sum formulas
# 1 + 2 + ... + n         = n(n+1)/2
# 1^2 + 2^2 + ... + n^2   = n(n+1)(2n+1)/6
# 1 + 3 + 5 + ... + (2n-1) = n^2
# geometric: a(r^n - 1)/(r - 1) for r != 1