主要来自here，我就只是补充了点东西，修改了一点东西，改了点 re 判断。
建议和我的快读一同使用，兼容的。
in，out兼容，不过建议in(a.val)，快一些。同理，建议out(a.val)
不行的话也有流输入输出的兼容。
除法是 \(O(\log mod)\) 的，嫌慢可以自行修改 inv() 函数内容。
template <int MOD> struct modint {int val;static int norm(const int& x) { return x < 0 ? x + MOD : x; }static constexpr int get_mod() { return MOD; }modint inv() const {assert(val);int a = val, b = MOD, u = 1, v = 0, t;while (b > 0) t = a / b, swap(a -= t * b, b), swap(u -= t * v, v);assert(b == 0);return modint(u);}modint() : val(0) {}modint(const int& m) : val(norm(m)) {}modint(const long long& m) : val(norm(m % MOD)) {}template<typename T> modint(const T m) : val(norm((long long)m % MOD)) {}template<class T> operator T() const { return val; }// 这个是类型强制转换，如果没用到而且很烦报错（可以跑，就只是报错）可以注释掉这一行modint operator-() const { return modint(norm(-val)); }bool operator==(const modint& o) { return val == o.val; }bool operator<(const modint& o) { return val < o.val; }bool operator>(const modint& o) { return val > o.val; }bool operator<=(const modint& o) { return val <= o.val; }bool operator>=(const modint& o) { return val >= o.val; }modint& operator+=(const modint& o) { return val = (1ll * val + o.val) % MOD, *this; }modint& operator-=(const modint& o) { return val = norm(1ll * val - o.val), *this; }modint& operator*=(const modint& o) { return val = static_cast<int>(1ll * val * o.val % MOD), *this; }modint& operator/=(const modint& o) { return *this *= o.inv(); }modint& operator%=(const modint& o) { return val %= o.val, *this; }modint& operator^=(const modint& o) { return val ^= o.val, *this; }modint& operator>>=(const modint& o) { return val >>= o.val, *this; }modint& operator<<=(const modint& o) { return val <<= o.val, *this; }modint operator-(const modint& o) const { return modint(*this) -= o; }modint operator+(const modint& o) const { return modint(*this) += o; }modint operator*(const modint& o) const { return modint(*this) *= o; }modint operator/(const modint& o) const { return modint(*this) /= o; }modint operator%(const modint& o) const { return modint(*this) %= o; }modint operator^(const modint& o) const { return modint(*this) ^= o; }modint operator>>(const modint& o) const { return modint(*this) >>= o; }modint operator<<(const modint& o) const { return modint(*this) <<= o; }friend std::istream& operator>>(std::istream& is, modint& a) {long long v;return is >> v, a.val = norm(v % MOD), is;}friend std::ostream& operator<<(std::ostream& os, const modint& a) { return os << a.val; }friend std::string tostring(const modint& a) { return std::to_string(a.val); }
};
using mint = modint<1000000009>;