大数模板，存档一下

template <ll M = ll(1e9 + 7)>
struct mod_int{
    ll x;
    mod_int(ll x = 0):x((x % M + M) % M){}
    mod_int operator + (mod_int b) const {return mod_int((x + b.x) % M);}
    mod_int operator - (mod_int b) const {return mod_int((x - b.x + M) % M);}
    mod_int operator * (mod_int b) const {return mod_int((x * b.x) % M);}
    mod_int operator / (mod_int b) const {return mod_int((x * b.inv().x) % M);}
    mod_int operator += (mod_int b) {return *this = *this + b;}
    mod_int operator -= (mod_int b) {return *this = *this - b;}
    mod_int operator *= (mod_int b) {return *this = *this * b;}
    mod_int operator /= (mod_int b) {return *this = *this / b;}
    mod_int operator - () const {return mod_int(-x);}
    mod_int operator ++ () const {return *this + 1;}
    mod_int operator -- () const {return *this - 1;}
    mod_int& operator= (const mod_int& b) {x = b.x; return *this;}
    mod_int& operator= (const int & b) {this->x = b; return *this;}
    bool operator == (mod_int b) const {return x == b.x;}
    bool operator != (mod_int b) const {return x != b.x;}
    friend ostream& operator << (ostream &out, const mod_int &a) {return out << a.x;}
    friend istream& operator >> (istream &in, mod_int &a) {return in >> a.x;}
    mod_int inv() const {
        ll a = x, b = M, u = 1, v = 0;
        while (b){
            ll t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        return mod_int(u);
    }

};