struct modint {
ll x;
modint() : x(0) {}
modint(ll x) : x(x) {}
bool operator==(modint y) { return x == y.x; }
void operator=(int y) {
y %= mod;
// cout << y << endl;
this->x = (y % mod);
}
modint operator+(modint y) {
modint z(x + y.x);
if (z.x >= mod)
z.x -= mod;
return z;
}
modint operator-(modint y) {
modint z(x - y.x);
if (z.x < 0)
z.x += mod;
return z;
}
};
modint operator*(modint x, ll y) {
modint z(x.x * y);
z.x %= mod;
return z;
}
modint operator*(ll y, modint x) {
modint z(x.x * y);
z.x %= mod;
return z;
}
modint operator*(modint x, modint y) {
modint z(x.x * y.x);
z.x %= mod;
return z;
}
ostream &operator<<(ostream &out, modint x) {
out << x.x;
return out;
}