#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 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) { using pii = pair; vector X(N); for (auto& x : X) { cin >> x.snd >> x.fst; if (x.snd == 1) { --x.fst; } } sort(X.begin(), X.end()); vec dp = make_v(N + 1, N + 1, mint(0)); dp[0][0] = 1; int gre = 0; for (int i = 0; i < N; i++) { for (int j = 0; j <= gre; j++) { int used = j + (i - gre); int rem = max(0, X[i].fst - used); if (X[i].snd == 0) { dp[i + 1][j] += dp[i][j] * rem; } else { dp[i + 1][j + 1] += dp[i][j] * rem; dp[i + 1][j] += dp[i][j]; } } if (X[i].snd == 1) { ++gre; } } mint res = 0; initFact(N + 10); for (int i = 0; i <= gre; i++) { mint way = dp[N][i] * fact[gre - i]; if (i % 2 == 0) { res += way; } else { res -= way; } } cout << res.value() << endl; } return 0; }