模板

int MOD; 
// const int MOD = ;
struct ModInt {
    int x;

    ModInt(int x = 0) : x(x % MOD) {}
    ModInt(long long x) : x (x % MOD) {}

    int val() { return x; }
    ModInt operator + (const ModInt &a) const { int x0 = x + a.x; return ModInt(x0 < MOD ? x0 : x0 - MOD); }
    ModInt operator - (const ModInt &a) const { int x0 = x - a.x; return ModInt(x0 < MOD ? x0 + MOD : x0); }
    ModInt operator * (const ModInt &a) const { return ModInt(1LL * x * a.x % MOD); }
    ModInt operator / (const ModInt &a) const { return *this * a.inv(); }
    void operator += (const ModInt &a) { x += a.x; if (x >= MOD) x -= MOD; }
    void operator -= (const ModInt &a) { x -= a.x; if (x < 0) x += MOD; }
    void operator *= (const ModInt &a) { x = 1LL * x * a.x % MOD; }
    void operator /= (const ModInt &a) { *this = *this / a; }
    ModInt qpow(long long n) const { ModInt res(1), mul(x);for (; n; n>>=1, mul *= mul)if (n & 1) res *= mul;return res; }
    ModInt inv() const { return qpow(MOD-2); }
    friend std::ostream &operator<<(std::ostream &os, const ModInt &a) { return os << a.x;}
};

使用

变量做模数时，使用 int MOD，常数做模数时，使用 const int MOD 。

可以像 int 一样使用。

支持的运算 ：

• +
• -
• *
• /
• +=
• -=
• *=
• /=
• qpow(n) 快速幂
• inv() 逆元

可以使用 std::cout 直接输出