[Some Tricks] 自动取模类

const i128 o = 1;
template < i64 mod, i64 invpow = mod - 2 >
struct Modular {
  u64 M = (o << 64) / mod;
  i64 query (i64 x) {
    u64 x_ = 1ull * x;
    u64 q = 1ull * (((i128) (M) * (i128) (x_)) >> 64);
    u64 r = x_ - q * (1ull * mod);
    return r >= mod ? 1ll * r - mod : 1ll * r;
  }
  i64 x;
  i64 norm (i64 v) {v = (v < 0) ? (v + mod) : v, v = (v >= mod) ? (v - mod) : v, v = (v >= mod) ? query (v) : v; return v;}
  i64 pow_mod (i64 a, i64 b) {i64 res = 1; for (i64 i = b; i > 0; i >>= 1, a = norm (a * a)) res = (i & 1) ? norm (res * a) : res; return res;}
  void init (i64 rhs) {x = norm (rhs); return ;}
  i64 val () {return norm (x);}
  void neg () {x = norm (mod - x); return ;}
  Modular inv () {assert (x != 0); auto res = *this; res.x = pow_mod (res.x, invpow); return res;}
  void add () {x = norm (x + 1); return ;}
  void sub () {x = norm (x - 1); return ;}
  Modular &operator += (Modular rhs) & {x = norm (x + rhs.x); return *this;}
  Modular &operator -= (Modular rhs) & {x = norm (x - rhs.x); return *this;}
  Modular &operator *= (Modular rhs) & {x = norm (x * rhs.x); return *this;}
  Modular &operator /= (Modular rhs) & {*this *= rhs.inv (); return *this;}
  Modular &operator += (i64 rhs) & {rhs = norm (rhs), x = norm (x + rhs); return *this;}
  Modular &operator -= (i64 rhs) & {rhs = norm (rhs), x = norm (x - rhs); return *this;}
  Modular &operator *= (i64 rhs) & {rhs = norm (rhs), x = norm (x * rhs); return *this;}
  Modular &operator /= (i64 rhs) & {rhs = norm (rhs), *this *= pow_mod (rhs, invpow); return *this;}  
  Modular &operator ^= (i64 ind) & {x = pow_mod (x, ind), x = (ind < 0) ? pow_mod (x, invpow) : x; return *this;}
  friend Modular operator + (Modular lhs, Modular rhs) {auto res = lhs; res += rhs; return res;}
  friend Modular operator - (Modular lhs, Modular rhs) {auto res = lhs; res -= rhs; return res;}
  friend Modular operator * (Modular lhs, Modular rhs) {auto res = lhs; res *= rhs; return res;}
  friend Modular operator / (Modular lhs, Modular rhs) {auto res = lhs; res /= rhs; return res;}
  friend Modular operator + (Modular lhs, i64 rhs) {auto res = lhs; rhs = norm (rhs); res.x = norm (res.x + rhs); return res;}
  friend Modular operator - (Modular lhs, i64 rhs) {auto res = lhs; rhs = norm (rhs); res.x = norm (res.x - rhs); return res;}
  friend Modular operator * (Modular lhs, i64 rhs) {auto res = lhs; rhs = norm (rhs); res.x = norm (res.x * rhs); return res;}
  friend Modular operator / (Modular lhs, i64 rhs) {auto res = lhs; rhs = norm (rhs); res.x = norm (res.x * pow_mod (rhs, invpow, mod)); return res;}  
  friend Modular operator ^ (Modular lhs, i64 ind) {auto res = lhs; res ^= ind; return res;}
  friend bool operator == (Modular lhs, Modular rhs) {return (lhs.val () == rhs.val ());}
  friend bool operator != (Modular lhs, Modular rhs) {return (lhs.val () != rhs.val ());}
  friend bool operator > (Modular lhs, Modular rhs) {return (lhs.val () > rhs.val ());}
  friend bool operator < (Modular lhs, Modular rhs) {return (lhs.val () < rhs.val ());}
  friend bool operator >= (Modular lhs, Modular rhs) {return (lhs.val () >= rhs.val ());}
  friend bool operator <= (Modular lhs, Modular rhs) {return (lhs.val () <= rhs.val ());} 
};