#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; #define fst first #define snd second /* clang-format off */ template struct _vec { using type = vector::type>; }; template struct _vec { using type = T; }; template using vec = typename _vec::type; template vector make_v(size_t size, const T& init) { return vector(size, init); } template auto make_v(size_t size, Ts... rest) { return vector(size, make_v(rest...)); } template inline void chmin(T &a, const T& b) { if (b < a) a = b; } template inline void chmax(T &a, const T& b) { if (b > a) a = b; } /* clang-format on */ template vector sumup(const vector& a) { int N = a.size(); vector res(N + 1); for (int i = 0; i < N; i++) res[i + 1] = res[i] + a[i]; return res; } template class modint { using u64 = std::uint_fast64_t; public: u64 a; constexpr modint(const u64 x = 0) noexcept : a(x % Modulus) { } constexpr u64 &value() noexcept { return a; } constexpr const u64 &value() const noexcept { return a; } constexpr modint operator+(const modint rhs) const noexcept { return modint(*this) += rhs; } constexpr modint operator-(const modint rhs) const noexcept { return modint(*this) -= rhs; } constexpr modint operator*(const modint rhs) const noexcept { return modint(*this) *= rhs; } constexpr modint operator/(const modint rhs) const noexcept { return modint(*this) /= rhs; } constexpr modint &operator+=(const modint rhs) noexcept { a += rhs.a; if (a >= Modulus) { a -= Modulus; } return *this; } constexpr modint &operator-=(const modint rhs) noexcept { if (a < rhs.a) { a += Modulus; } a -= rhs.a; return *this; } constexpr modint &operator*=(const modint rhs) noexcept { a = a * rhs.a % Modulus; return *this; } constexpr modint &operator/=(const modint rhs) noexcept { return *this *= ~rhs; } constexpr modint power(u64 exp) const noexcept { modint v = 1, x = *this; while (exp) { if (exp & 1) { v *= x; } x *= x; exp >>= 1; } return v; } constexpr modint operator~() const noexcept { return power(Modulus - 2); } }; using mint = modint<1000000007>; vector fact, factInv; void initFact(int N) { fact.resize(N + 1); factInv.resize(N + 1); fact[0] = 1; for (int i = 1; i <= N; i++) fact[i] = fact[i - 1] * i; factInv[N] = ~fact[N]; for (int i = N - 1; i >= 0; i--) factInv[i] = factInv[i + 1] * (i + 1); } int main() { #ifdef DEBUG ifstream ifs("in.txt"); cin.rdbuf(ifs.rdbuf()); #endif int N; while (cin >> N) { initFact(4000); vector X(N, 0), Y(N, 0); int xs = 0, ys = 0; for (int i = 0; i < N; i++) { int t, x; cin >> t >> x; --x; if (t == 0) { ++X[x]; ++xs; } else { ++Y[x]; ++ys; } } auto sumX = sumup(X), sumY = sumup(Y); vector dp(N + 1, 0); dp[0] = 1; for (int p = 0; p < N; p++) { vector ndp(N + 1, 0); for (int y = 0; y <= p; y++) { for (int add = 0; add < 2; add++) { int ny = y + add; mint way = 1; if (add) { way *= max(0, sumY[p + 1] - y); } if (p + 1 - ny - sumX[p + 1] >= 0) { way *= fact[p + 1 - ny - sumX[p]]; way /= fact[p + 1 - ny - sumX[p + 1]]; } else { way = 0; } ndp[ny] += dp[y] * way; } } dp.swap(ndp); } cout << dp[ys].value() << endl; } return 0; }