Modulo
Jump to navigation
Jump to search
template<int MOD>
struct ModInt {
static const int Mod = MOD;
unsigned x;
ModInt() : x(0) {}
ModInt(signed sig) {
int sigt = sig % MOD;
if (sigt < 0) sigt += MOD;
x = sigt;
}
ModInt(signed long long sig) {
int sigt = sig % MOD;
if (sigt < 0) sigt += MOD;
x = sigt;
}
int get() const { return (int) x; }
ModInt &operator+=(ModInt that) {
if ((x += that.x) >= MOD) x -= MOD;
return *this;
}
ModInt &operator-=(ModInt that) {
if ((x += MOD - that.x) >= MOD) x -= MOD;
return *this;
}
ModInt &operator*=(ModInt that) {
x = (unsigned long long) x * that.x % MOD;
return *this;
}
ModInt &operator/=(ModInt that) {
(*this) *= (that ^ (MOD - 2));
return *this;
}
ModInt operator^(int n) const {
ModInt r = ModInt(1);
ModInt a = ModInt(*this);
while (n) {
if (n & 1) r *= a;
n >>= 1;
a *= a;
}
return r;
}
ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
ModInt operator/(ModInt that) const { return ModInt(*this) /= that; }
};
typedef ModInt<1000000007> mint;