组合数学

自动取模型

template<int mod>
struct ModZ{
	LL x;
	ModZ(LL t = 0) {t %= mod; if (t < mod) t += mod; x = t;}
	
	ModZ power(ModZ a, LL b) {ModZ res = 1; for (; b; b >>= 1, a *= a) if (b & 1) res *= a; return res;}
	
	ModZ operator + (const ModZ& r) const {return ModZ(x + r.x);}
	ModZ operator - (const ModZ& r) const {return ModZ(x - r.x);}
	ModZ operator * (const ModZ& r) const {return ModZ(x * r.x);}
	ModZ operator / (const ModZ& r) const {return ModZ(x * power(r.x, mod - 2));}
	
	ModZ &operator += (const ModZ& r) const {return ModZ(x + r.x);}
	ModZ &operator -= (const ModZ& r) const {return ModZ(x - r.x);}
	ModZ &operator *= (const ModZ& r) const {return ModZ(x * r.x);}
	ModZ &operator /= (const ModZ& r) const {return ModZ(x / r.x);}
	
	friend istream &operator >> (istream &is, ModZ &a) {LL v; is >> v; a = ModZ(v); return is;}
	friend ostream &operator << (ostream &os, const ModZ& r) {os << r.x; return os;}
	
	friend bool operator == (ModZ lhs, ModZ rhs) {return lhs.x == rhs.x;}
	friend bool operator != (ModZ lhs, ModZ rhs) {return lhs.x != rhs.x;}
};
typedef ModZ<998244353> Z;