运算中自动完成取模.

template <int M>
struct ModInt {
    static_assert(M > 1, "Mod mast be larger than 1");

private:
    int val;

    ModInt inv() const {
        return pow(M - 2);
    }

public:
    ModInt() : val() {}
    ModInt(long long x) {
        x %= M;
        if (x < 0)
            x += M;
        val = x;
    }
    ModInt pow(long long k) const {
        ModInt a = *this;
        ModInt res = 1;
        if (k < 0)
            k = -k, a = 1 / a;
        while (k) {
            if (k & 1)
                res *= a;
            a *= a;
            k >>= 1;
        }
        return res;
    }
    friend ModInt operator+(const ModInt &a, const ModInt &b) {
        ModInt res;
        res.val = a.val + b.val;
        if (res.val > M)
            res.val -= M;
        return res;
    }
    friend ModInt operator-(const ModInt &a, const ModInt &b) {
        ModInt res;
        if (a.val < b.val) {
            res.val = a.val - b.val + M;
        } else {
            res.val = a.val - b.val;
        }
        return res;
    }
    friend ModInt operator*(const ModInt &a, const ModInt &b) {
        return 1LL * a.val * b.val % M;
    }
    friend ModInt operator/(const ModInt &a, const ModInt &b) {
        return a * b.inv();
    }
    ModInt &operator+=(const ModInt &a) {
        val += a.val;
        if (val > M)
            val -= M;
        return *this;
    }
    ModInt &operator-=(const ModInt &a) {
        val -= a.val;
        if (val < 0)
            val += M;
        return *this;
    }
    ModInt &operator*=(const ModInt &a) {
        val = 1LL * val * a.val % M;
        return *this;
    }
    ModInt &operator/=(const ModInt &a) {
        *this *= a.inv();
        return *this;
    }
    ModInt operator+() {
        return *this;
    }
    ModInt operator-() {
        ModInt res;
        if (val)
            res.val = M - val;
        return res;
    }
    ModInt &operator++() {
        val++;
        if (val == M)
            val = 0;
        return *this;
    }
    ModInt operator++(int) {
        ModInt tmp = *this;
        ++*this;
        return tmp;
    }
    ModInt &operator--() {
        val--;
        if (val == -1)
            val = M - 1;
        return *this;
    }
    ModInt operator--(int) {
        ModInt tmp = *this;
        --*this;
        return tmp;
    }
    bool operator==(const ModInt &a) const {
        return this->val == a.val;
    }
    friend std::istream &operator>>(std::istream &cin, ModInt &a) {
        long long x;
        cin >> x;
        a = x;
        return cin;
    }
    friend std::ostream &operator<<(std::ostream &cout, const ModInt &a) {
        cout << a.val;
        return cout;
    }
};

// using Mint = ModInt<Mod>;