text: template <unsigned int mod_>
  struct ModInt
  {
      using uint = unsigned int;
      using ll = long long;
      using ull = unsigned long long;
  
      constexpr static uint mod = mod_;
  
      uint v;
      ModInt() : v(0) {}
      ModInt(ll v) : v(normS(v % mod + mod)) {}
      explicit operator bool() const { return v != 0; }
      static uint normS(const uint &x) { return (x < mod) ? x : x - mod; } // [0 , 2*mod-1] -> [0 , mod-1]
      static ModInt make(const uint &x)
      {
          ModInt m;
          m.v = x;
          return m;
      }
      ModInt operator+(const ModInt &b) const { return make(normS(v + b.v)); }
      ModInt operator-(const ModInt &b) const { return make(normS(v + mod - b.v)); }
      ModInt operator-() const { return make(normS(mod - v)); }
      ModInt operator*(const ModInt &b) const { return make((ull)v * b.v % mod); }
      ModInt operator/(const ModInt &b) const { return *this * b.inv(); }
      ModInt &operator+=(const ModInt &b) { return *this = *this + b; }
      ModInt &operator-=(const ModInt &b) { return *this = *this - b; }
      ModInt &operator*=(const ModInt &b) { return *this = *this * b; }
      ModInt &operator/=(const ModInt &b) { return *this = *this / b; }
      ll extgcd(ll a, ll b, ll &x, ll &y) const
      {
          ll u[] = {a, 1, 0}, v[] = {b, 0, 1};
          while (*v)
          {
              ll t = *u / *v;
              for (int i = 0; i < 3; i++)
              {
                  swap(u[i] -= t * v[i], v[i]);
              }
          }
          if (u[0] < 0)
          {
              for (int i = 0; i < 3; i++)
              {
                  u[i] = -u[i];
              }
          }
          x = u[1], y = u[2];
          return u[0];
      }
      ModInt inv() const
      {
          ll x, y;
          extgcd(v, mod, x, y);
          return make(normS(x + mod));
      }
      bool operator==(const ModInt &b) const { return v == b.v; }
      bool operator!=(const ModInt &b) const { return v != b.v; }
      friend istream &operator>>(istream &o, ModInt &x)
      {
          ll tmp;
          o >> tmp;
          x = ModInt(tmp);
          return o;
      }
      friend ostream &operator<<(ostream &o, const ModInt &x) { return o << x.v; }
  };
  using mint = ModInt<1000000007>;