大数模板，存档一下
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);
}
};