#include #define rep(i, n) for (lli i = 0; i < (n); i++) #define rrep(i, n) for (lli i = (n)-1; i >= 0; i--) using namespace std; using lli = long long int; void YESNO(bool), YesNo(bool); template bool chmin(T1 &l, const T2 &r); template bool chmax(T1 &l, const T2 &r); template struct mod_int { constexpr static signed MODULO = M; constexpr static unsigned TABLE_SIZE = T; signed x; mod_int() : x(0) {} mod_int(long long y) : x(static_cast(y >= 0 ? y % MODULO : MODULO - (-y) % MODULO)) {} mod_int(int y) : x(y >= 0 ? y % MODULO : MODULO - (-y) % MODULO) {} mod_int &operator+=(const mod_int &rhs) { if ((x += rhs.x) >= MODULO) x -= MODULO; return *this; } mod_int &operator-=(const mod_int &rhs) { if ((x += MODULO - rhs.x) >= MODULO) x -= MODULO; return *this; } mod_int &operator*=(const mod_int &rhs) { x = static_cast(1LL * x * rhs.x % MODULO); return *this; } mod_int &operator/=(const mod_int &rhs) { x = static_cast((1LL * x * rhs.inv().x) % MODULO); return *this; } mod_int operator-() const { return mod_int(-x); } mod_int operator+(const mod_int &rhs) const { return mod_int(*this) += rhs; } mod_int operator-(const mod_int &rhs) const { return mod_int(*this) -= rhs; } mod_int operator*(const mod_int &rhs) const { return mod_int(*this) *= rhs; } mod_int operator/(const mod_int &rhs) const { return mod_int(*this) /= rhs; } bool operator<(const mod_int &rhs) const { return x < rhs.x; } mod_int inv() const { assert(x != 0); if (x <= static_cast(TABLE_SIZE)) { if (_inv[1].x == 0) prepare(); return _inv[x]; } else { signed a = x, b = MODULO, u = 1, v = 0, t; while (b) { t = a / b; a -= t * b; std::swap(a, b); u -= t * v; std::swap(u, v); } return mod_int(u); } } mod_int pow(long long t) const { assert(!(x == 0 && t == 0)); mod_int e = *this, res = mod_int(1); for (; t; e *= e, t >>= 1) if (t & 1) res *= e; return res; } mod_int fact() { if (_fact[0].x == 0) prepare(); return _fact[x]; } mod_int inv_fact() { if (_fact[0].x == 0) prepare(); return _inv_fact[x]; } mod_int choose(mod_int y) { assert(y.x <= x); return this->fact() * y.inv_fact() * mod_int(x - y.x).inv_fact(); } static mod_int _inv[TABLE_SIZE + 1]; static mod_int _fact[TABLE_SIZE + 1]; static mod_int _inv_fact[TABLE_SIZE + 1]; static void prepare() { _inv[1] = 1; for (int i = 2; i <= (int)TABLE_SIZE; ++i) { _inv[i] = 1LL * _inv[MODULO % i].x * (MODULO - MODULO / i) % MODULO; } _fact[0] = 1; for (unsigned i = 1; i <= TABLE_SIZE; ++i) { _fact[i] = _fact[i - 1] * int(i); } _inv_fact[TABLE_SIZE] = _fact[TABLE_SIZE].inv(); for (int i = (int)TABLE_SIZE - 1; i >= 0; --i) { _inv_fact[i] = _inv_fact[i + 1] * (i + 1); } } }; template std::ostream &operator<<(std::ostream &os, const mod_int &rhs) { return os << rhs.x; } template std::istream &operator>>(std::istream &is, mod_int &rhs) { long long s; is >> s; rhs = mod_int(s); return is; } template mod_int mod_int::_inv[TABLE_SIZE + 1]; template mod_int mod_int::_fact[TABLE_SIZE + 1]; template mod_int mod_int::_inv_fact[TABLE_SIZE + 1]; template bool operator==(const mod_int &lhs, const mod_int &rhs) { return lhs.x == rhs.x; } template bool operator!=(const mod_int &lhs, const mod_int &rhs) { return !(lhs == rhs); } const int MF = 100005; //割り算しないなら const int MOD = 1000000007; using mint = mod_int; mint binom(int n, int r) { return (r < 0 || r > n || n < 0) ? 0 : mint(n).choose(r); } mint fact(int n) { return mint(n).fact(); } mint inv_fact(int n) { return mint(n).inv_fact(); } mint dp[3005][3005]; // dp[i][j] := type 0の条件をi個満たしている, type 1の条件をj個満たしている int main() { int n; cin >> n; vector t(n), X(n); vector u[2]; rep(i, n) cin >> t[i] >> X[i]; rep(i, n) u[t[i]].push_back(X[i] - 1); rep(i, 2) sort(u[i].begin(), u[i].end()); dp[0][0] = 1; rep(i, n) { // insert i vector v[2]; for (auto s : u[0]) if (i <= s) v[0].push_back(s); for (auto s : u[1]) if (i >= s) v[1].push_back(s); rep(a, v[1].size() + 1) { if (i < a) continue; lli b = i - a; // a個条件を満たしている, b個条件を満たしていいる // type 0:v[0].size()の中からまだ使われてないものを使う sz-a // type 1:使えるもののうちあんまりX[i]が大きいのを使ってしまうとあとから困るかも // 選択肢は? のこりu[1].size()-(b+1)個おく必要があるが dp[a + 1][b] += dp[a][b] * (mint((lli)v[1].size() - a)); if (b < u[0].size()) dp[a][b + 1] += dp[a][b] * (mint((lli)v[0].size()) - mint((lli)u[0].size() - (b + 1))); } } mint ret = 0; rep(i, n + 1) ret += dp[n - i][i]; cout << ret << endl; } // -- lib void YESNO(bool b) { cout << (b ? "YES" : "NO") << endl; } void YesNo(bool b) { cout << (b ? "Yes" : "No") << endl; } template bool chmin(T1 &l, const T2 &r) { return (l > r) ? (l = r, true) : false; } template bool chmax(T1 &l, const T2 &r) { return (l < r) ? (l = r, true) : false; }