//貪欲+包除 #include #include #include #define rep(i, n) for(i = 0; i < n; i++) #define int long long using namespace std; typedef pair P; int mod = 1000000007; int n; int t[3000], x[3000]; int rt[3001]; //rt[i] = t[0] + … + t[i - 1] int dp[3001][3001]; //dp[i][j] = 個数 (t[i] == 0:全部守る. t[i] == 1: j個を選んで違反. それ以外は違反してもしなくてもいい(1通りとして後回し).) int fact[3001]; signed main() { int i, j; cin >> n; rep(i, n) cin >> t[i] >> x[i]; P pa[3000]; rep(i, n) { if (t[i] == 0) pa[i] = P(x[i], t[i]); else pa[i] = P(x[i] - 1, t[i]); } sort(pa, pa + n); rep(i, n) { t[i] = pa[i].second; x[i] = pa[i].first; } rep(i, n) { rt[i + 1] = rt[i] + t[i]; } //rep(i, n) { cout << t[i] << ", " << x[i] << endl; } dp[0][0] = 1; rep(i, n) { rep(j, rt[i] + 1) { int tempura = i - (rt[i] - j); if (t[i] == 0) { if (x[i] - tempura > 0) { dp[i + 1][j] += dp[i][j] * (x[i] - tempura); dp[i + 1][j] %= mod; } } else { dp[i + 1][j] += dp[i][j]; dp[i + 1][j] %= mod; if (x[i] - tempura > 0) { dp[i + 1][j + 1] += dp[i][j] * (x[i] - tempura); dp[i + 1][j + 1] %= mod; } } } } /*rep(i, n + 1) { rep(j, i + 1) { cout << dp[i][j] << " "; } cout << endl; }*/ fact[0] = 1; rep(i, n) { fact[i + 1] = (i + 1) * fact[i] % mod; } int ans = 0; rep(j, rt[n] + 1) { int res = dp[n][j]; res *= fact[rt[n] - j]; res %= mod; if (j % 2 == 0) { ans += res; } else { ans += mod - res; } ans %= mod; } cout << ans << endl; return 0; }