int add(int a, int b, int mod) {
    return ((a % mod) + (b % mod)) % mod;
}

int mul(int a, int b, int mod) {
    return ((a % mod) * (b % mod)) % mod;
}

int sub(int a, int b, int mod) {
    return ((a % mod) - (b % mod) + mod) % mod;
}

int GCD(int a, int b) {
    return b == 0 ? a : GCD(b, a % b);
}

int LCM(int a, int b) {
    return a / GCD(a, b) * b;
}

int fast_power_recursive(int b, int p) {
    if (!p)
        return 1;
    int r = fast_power_recursive(b, p / 2);
    r *= r;
    if (p & 1)
        r *= b;
    return r;
}

int fast_power_iterative(int a, int b) {
    int ret = 1;
    while (b > 0) {
        if (b & 1)
            ret *= a;
        a = a * a;
        b /= 2;
    }
    return ret;
}