// Potencia rápida, recursiva.
#ifndef POWER_H
#define POWER_H

// Devuelve b^e mod m, con e >= 0, b >= 0 y 1 <= m <= 2^31.
// Como cada factor es menor que m, un producto es menor que 2^62 y cabe en long long.
// Si multiplications no es nulo, le suma cuántos productos se hicieron.
inline long long power_mod(long long b, long long e, long long m, long long* multiplications = nullptr) {
    if (e == 0) {
        return 1 % m;
    }
    long long half = power_mod(b, e / 2, m, multiplications);
    long long result = half * half % m;
    if (multiplications) (*multiplications)++;
    if (e % 2 == 1) {
        result = result * (b % m) % m;
        if (multiplications) (*multiplications)++;
    }
    return result;
}

#endif