1

ModInt<1000000007> mi = 0;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

template <int Mod>
class ModInt {
public:
  int n;
  constexpr ModInt(const int x = 0) noexcept : n((x % Mod + Mod) % Mod) {}
  constexpr int &value() noexcept { return n; }
  constexpr const int &value() const noexcept { return n; }
  constexpr ModInt operator+(const ModInt rhs) const noexcept { return ModInt(*this) += rhs; }
  constexpr ModInt operator-(const ModInt rhs) const noexcept {    return ModInt(*this) -= rhs;  }
  constexpr ModInt operator*(const ModInt rhs) const noexcept {    return ModInt(*this) *= rhs;  }
  constexpr ModInt operator/(const ModInt rhs) const noexcept {    return ModInt(*this) /= rhs;  }
  constexpr ModInt &operator+=(const ModInt rhs) noexcept {
    n += rhs.n;
    if (n >= Mod)
      n -= Mod;
    return *this;
  }
  constexpr ModInt &operator-=(const ModInt rhs) noexcept {
    if (n < rhs.n)
      n += Mod;
    n -= rhs.n;
    return *this;
  }
  constexpr ModInt &operator*=(const ModInt rhs) noexcept {
    n = n * rhs.n % Mod;
    return *this;
  }
  constexpr ModInt &operator/=(ModInt rhs) noexcept {
    int exp = Mod - 2;
    while (exp) {
      if (exp % 2)
        *this *= rhs;
      rhs *= rhs;
      exp /= 2;
    }
    return *this;
  }
  friend std::istream &operator>>(std::istream &_istr, ModInt &rhs) {
    _istr >> rhs.n;
    rhs.n = (rhs.n % Mod + Mod) % Mod;
    return _istr;
  }
  friend std::ostream &operator<<(std::ostream &_ostr, const ModInt &rhs) {
    return _ostr << rhs.n;
  }
};