modular.cpp

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const ll MOD = 1000000009;

ll Pow(ll a, ll b) {
    ll x = 1, y = a;
    while (b) {
        if (b % 2) (x *= y) %= MOD;
        (y *= y) %= MOD;
        b /= 2;
    }
    return x;
}

ll Inv(ll x) {
    return Pow(x, MOD - 2);
}

struct Mod {
    ll x;

    Mod () {}

    Mod (ll _x) {
        x = _x % MOD;
        if (x < 0) x += MOD;
    }

    Mod operator+ (Mod rhs) {
        ll ans = x + rhs.x;
        if (ans >= MOD) ans -= MOD;
        Mod ret; ret.x = ans; return ret;
    }

    Mod operator- (Mod rhs) {
        ll ans = x - rhs.x;
        if (ans < 0) ans += MOD;
        Mod ret; ret.x = ans; return ret;
    }

    Mod operator* (Mod rhs) {
        Mod ret; ret.x = x * rhs.x % MOD; return ret;
    }

    Mod operator+= (Mod rhs) {
        x += rhs.x;
        if (x >= MOD) x -= MOD;
        return *this;
    }

    Mod operator-= (Mod rhs) {
        x -= rhs.x;
        if (x < 0) x += MOD;
        return *this;
    }

    Mod operator*= (Mod rhs) {
        x *= rhs.x;
        x %= MOD;
        return *this;
    }

    Mod operator^ (ll a) {
        Mod ret; ret.x = Pow(x, a); return ret;
    }

    Mod operator^= (ll a) {
        x = Pow(x, a);
        return *this;
    }

    Mod inv() {
        Mod ret; ret.x = Inv(x); return ret;
    }

    Mod operator/ (Mod rhs) {
        return *this * rhs.inv();
    }

    Mod operator/= (Mod rhs) {
        *this *= rhs.inv();
        return *this;
    }
};

Mod operator+ (ll a, Mod b) {
    return Mod(a) + b;
}

Mod operator- (ll a, Mod b) {
    return Mod(a) - b;
}

Mod operator* (ll a, Mod b) {
    return Mod(a) * b;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); 
    srand((unsigned)chrono::high_resolution_clock::now().time_since_epoch().count());
}