// #define DEBUGGING #include #define endl '\n' #define ALL(v) std::begin(v), std::end(v) #define ALLR(v) std::rbegin(v), std::rend(v) using ll = std::int64_t; using ull = std::uint64_t; using pll = std::pair; using tll = std::tuple; template using vec = std::vector; template using vvec = vec>; template const T& var_min(const T &t) { return t; } template const T& var_max(const T &t) { return t; } template const T& var_min(const T &t, const Tail&... tail) { return std::min(t, var_min(tail...)); } template const T& var_max(const T &t, const Tail&... tail) { return std::max(t, var_max(tail...)); } template void chmin(T &t, const Tail&... tail) { t = var_min(t, tail...); } template void chmax(T &t, const Tail&... tail) { t = var_max(t, tail...); } template const T& clamp(const T &t, const T &low, const T &high) { return std::max(low, std::min(high, t)); } template void chclamp(T &t, const T &low, const T &high) { return t = clamp(t, low, high); } namespace init__ { struct InitIO { InitIO() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); std::cout << std::fixed << std::setprecision(30); } } init_io; } #define mv_rec make_v(init, tail...) template T make_v(T init) { return init; } template auto make_v(T init, size_t s, Tail... tail) { return vec(s, mv_rec); } #undef mv_rec #ifdef DEBUGGING #else #define DEBUG(...) 0 #define DEBUG_SEPARATOR_LINE 0 #endif namespace math { template constexpr T pow(const T &n, ll k) { T ret = n.mul_id_ele(); T cur = n; while (k) { if (k & 1) ret *= cur; cur *= cur; k /= 2; } return ret; } } namespace math { template struct Modint { constexpr Modint(ll x) : x(x % Mod) { } constexpr Modint() : Modint(0) { } constexpr Modint add_id_ele() const { return Modint(0); } constexpr Modint mul_id_ele() const { return Modint(1); } constexpr ll& value() { return x; } constexpr ll value() const { return x; } constexpr Modint& operator +=(const Modint &oth) { x += oth.value(); if (Mod < x) x -= Mod; return *this; } constexpr Modint& operator -=(const Modint &oth) { x += Mod - oth.value(); if (Mod < x) x -= Mod; return *this; } constexpr Modint& operator *=(const Modint &oth) { x *= oth.value(); x %= Mod; return *this; } constexpr Modint& operator /=(const Modint &oth) { x *= oth.inv(); x %= Mod; return *this; } constexpr Modint operator +(const Modint &oth) const { return Modint(x) += oth; } constexpr Modint operator -(const Modint &oth) const { return Modint(x) -= oth; } constexpr Modint operator *(const Modint &oth) const { return Modint(x) *= oth; } constexpr Modint operator /(const Modint &oth) const { return Modint(x) /= oth; } constexpr Modint operator -() const { return Modint((x != 0) * (Mod - x)); } template constexpr typename std::enable_if::value, const Modint&>::type operator =(T t) { (*this) = Modint(std::forward(t)); return *this; } constexpr Modint inv() const { return ::math::pow(*this, Mod - 2); } constexpr ll mod() const { return Mod; } private: ll x; }; } namespace math { template class Combination { using mint = Modint; ssize_t maxv; vec factv, ifactv; public: Combination(ssize_t maxv) : maxv(maxv), factv(maxv + 1), ifactv(maxv + 1) { factv[0] = mint(1); for (ll i = 1; i <= maxv; i++) factv[i] = factv[i - 1] * i; ifactv.back() = factv.back().inv(); for (ll i = maxv - 1; 0 <= i; i--) ifactv[i] = ifactv[i + 1] * (i + 1); } mint fact(ll n) const { return factv[n]; } mint ifact(ll n) const { return ifactv[n]; } mint perm(ll n, ll k) const { return factv[n] * ifactv[n - k]; } mint comb(ll n, ll k) const { return perm(n, k) * ifactv[k]; } }; } constexpr ll mod = 1e9 + 7; using mint = math::Modint; using namespace std; const size_t SIZE = 3010; mint dp[SIZE][SIZE]; // not used down arrow int main() { math::Combination C(SIZE * 10); ll n; cin >> n; vec tx(n); for (auto &&e : tx) { ll t, x; cin >> t >> x; e = pll(t, x); } vec cnts(n + 1); for (ll i = 0; i < n; i++) { ll t, x; tie(t, x) = tx[i]; x--; (t == 0 ? cnts[x].first : cnts[x].second)++; } dp[0][0] = 1; ll up_sum = 0, down_sum = 0; for (ll i = 0; i < n; i++) { ll a, b; tie(a, b) = cnts[i]; DEBUG(a, b); for (ll j = 0; j <= down_sum; j++) { ll rest = ((i + 1) - up_sum) - (down_sum - j); DEBUG(rest); if (j + b && a <= rest - 1) { mint c(j + b); c *= C.comb(rest - 1, a); DEBUG(j + b, rest - 1, a, C.comb(rest - 1, a).value()); dp[i + 1][j + b - 1] += dp[i][j] * c; } if (a <= rest) { dp[i + 1][j + b] += dp[i][j] * C.comb(rest, a); } } up_sum += a; down_sum += b; } cout << dp[n][0].value() << endl; return 0; }