Hello Codeforces!

I’m going to introduce you to a C++ struct that helps you easily forget MOD, instead of always being nervous about it.

Using this struct, you can easily add, subtract, multiply, divide, and raise to a power without thinking about overflow or missing MOD. Everything is considered in it. This is very easy to use; copy, paste, and use. Let’s see a few examples.

(a + b) % MOD

a + b

(a — b + MOD) % MOD

a — b

a * b % MOD

a * b

a / b

a.pow(b)

Let's look at a real problem, 296B - Yaroslav and Two Strings. The following is the old solution (20869331) without using Mint:

int sbet = 1, pbet = 1, mos = 1;
for(int i = 0; i < n; i++)
    sbet = (ll) sbet * bet(s[i], p[i]) % mod,
        pbet = (ll) pbet * bet(p[i], s[i]) % mod,
        mos = (ll) mos * eq(p[i], s[i]) % mod;
int ans = 1;
int b = count(s.begin(), s.end(), '?') + count(p.begin(), p.end(), '?');
for(int a = 10; b; b >>= 1, a = (ll) a * a % mod)
    if(b & 1)
        ans = (ll) ans * a % mod;
(ans += mos) %= mod;
(ans -= sbet — mod) %= mod;
(ans -= pbet — mod)  %= mod;
cout << ans << '\n';

But now, see how clean the new version (351365035) is:

Mint sbet = 1, pbet = 1, mos = 1;
for (int i = 0; i < n; i++) {
    sbet *= bet(s[i], p[i]);
    pbet *= bet(p[i], s[i]);
    mos *= eq(p[i], s[i]);
}
Mint ans = Mint(10).pow(count(s.begin(), s.end(), '?') + count(p.begin(), p.end(), '?'));
cout << ans + mos - sbet - pbet << '\n';

More examples:

• Compare 62786218 with 351366321.
• Compare 52551573 with 351159739.

Benefits of the Mint struct:

• You never need to use MOD in your code.
• Operations with int and Mint are handled safely. Like 2 + x, x + 2, x / 2, all of them work.
• Takes modulo only once, in its constructor.
• Short, easy to implement if you want to type it (like in ICPC) or remember it.

Also, there is an appendix to the Mint struct which makes the factorials and comb function, which are useful in a lot of cases.

I've been using this for several years, and you can be sure it works fine.

typedef long long ll;
constexpr int MAX_N = 1e6 + 14, MOD = 1000000007;

struct Mint {
    int x;

    Mint(ll x = 0) : x((x % MOD + MOD) % MOD) {
    }

    explicit operator int() const {
        return x;
    }

    bool operator==(const Mint& rhs) const {
        return x == rhs.x;
    }

    bool operator!=(const Mint& rhs) const {
        return !(rhs == *this);
    }

    friend Mint operator+(const Mint& l, const Mint& r) {
        return l.x + r.x;
    }

    Mint& operator+=(const Mint& o) {
        return *this = *this + o;
    }

    friend Mint operator-(const Mint& l, const Mint& r) {
        return l.x - r.x;
    }

    Mint operator-() const {
        return -x;
    }

    Mint& operator-=(const Mint& o) {
        return *this = *this - o;
    }

    friend Mint operator*(const Mint& l, const Mint& r) {
        return (ll)l.x * r.x;
    }

    Mint& operator*=(const Mint& o) {
        return *this = *this * o;
    }

    Mint pow(ll b) const {
        Mint ans = 1;
        Mint a = *this;
        for (; b; b >>= 1, a = a * a)
            if (b & 1)
                ans *= a;
        return ans;
    }

    friend Mint operator/(const Mint& l, const Mint& r) {
        return l * r.pow(MOD - 2);
    }

    Mint& operator/=(const Mint& o) {
        return *this = *this / o;
    }

    friend ostream& operator<<(ostream& os, const Mint& o) {
        return os << o.x;
    }
};

Mint fac[MAX_N] = {1}, rfac[MAX_N] = {1};

void prep() {
    for (int i = 1; i < MAX_N; ++i)
        fac[i] = fac[i &mdash; 1] * i;
    rfac[MAX_N &mdash; 1] = 1 / fac[MAX_N &mdash; 1];
    for (int i = MAX_N &mdash; 2; i >= 0; --i)
        rfac[i] = (i + 1) * rfac[i + 1];
}

Mint c(int n, int r) {
    return n < r || r < 0 ? 0 : fac[n] * rfac[r] * rfac[n &mdash; r];
}

If you want to copy/paste, use this.