pub fn powmod(x: u64, p: u64, m: u64) -> u64 {
    let mut res = x;
    for _ in 1..p {
        res = (res * x) % m;
    }
    return res;
}

pub fn adler64(buf: &[u8]) -> u64 {
    let mod64 = 4294967291u64;
    let mut s1 = 1u64;
    let mut s2 = 0u64;

    for n in buf {
        s1 = (s1 + *n as u64) % mod64;
        s2 = (s2 + s1) % mod64;
    }
    return (s2 << 32) | s1;
}

pub fn inverse_mod(x: i64, m: i64) -> i64 {
    let (_, x, _) = extended_gcd(x, m);
    return (x % m + m) % m;
}

pub fn extended_gcd(a: i64, b: i64) -> (i64, i64, i64) {
    if a == 0 {
        return (b, 0, 1);
    }
    let (d, x, y) = extended_gcd(b % a, a);
    return (d, y - (b / a) * x, x);
}