Modular exponentiation

modexp.c

// return (b ^ e) % m
uint64_t modexp(uint64_t b, uint64_t e, uint64_t m = 1000000007) {
    uint64_t r = 1;
    while (e) {
        if (e & 1)
            r = (r * b) % m;
        b = (b * b) % m;
        e >>= 1;
    }
    return r;
}