// ---------- begin ModInt ---------- const MOD: u32 = 1_000_000_007; #[derive(Clone, Copy)] struct ModInt(u32); impl std::ops::Add for ModInt { type Output = ModInt; fn add(self, rhs: ModInt) -> Self::Output { let mut d = self.0 + rhs.0; if d >= MOD { d -= MOD; } ModInt(d) } } impl std::ops::AddAssign for ModInt { fn add_assign(&mut self, rhs: ModInt) { *self = *self + rhs; } } impl std::ops::Sub for ModInt { type Output = ModInt; fn sub(self, rhs: ModInt) -> Self::Output { let mut d = self.0 + MOD - rhs.0; if d >= MOD { d -= MOD; } ModInt(d) } } impl std::ops::SubAssign for ModInt { fn sub_assign(&mut self, rhs: ModInt) { *self = *self - rhs; } } impl std::ops::Mul for ModInt { type Output = ModInt; fn mul(self, rhs: ModInt) -> Self::Output { ModInt((self.0 as u64 * rhs.0 as u64 % MOD as u64) as u32) } } impl std::ops::MulAssign for ModInt { fn mul_assign(&mut self, rhs: ModInt) { *self = *self * rhs; } } impl std::ops::Neg for ModInt { type Output = ModInt; fn neg(self) -> Self::Output { ModInt(if self.0 == 0 {0} else {MOD - self.0}) } } impl std::fmt::Display for ModInt { fn fmt<'a>(&self, f: &mut std::fmt::Formatter<'a>) -> std::fmt::Result { write!(f, "{}", self.0) } } impl std::str::FromStr for ModInt { type Err = std::num::ParseIntError; fn from_str(s: &str) -> Result { let val = s.parse::()?; Ok(ModInt::new(val)) } } impl From for ModInt { fn from(val: usize) -> Self { ModInt((val % MOD as usize) as u32) } } #[allow(dead_code)] impl ModInt { pub fn new(n: u32) -> ModInt { ModInt(n % MOD) } pub fn zero() -> ModInt { ModInt(0) } pub fn one() -> ModInt { ModInt(1) } pub fn pow(self, mut n: u32) -> ModInt { let mut t = ModInt::one(); let mut s = self; while n > 0 { if n & 1 == 1 { t *= s; } s *= s; n >>= 1; } t } pub fn inv(self) -> ModInt { assert!(self.0 > 0); self.pow(MOD - 2) } } // ---------- end ModInt ---------- // ---------- begin Precalc ---------- #[allow(dead_code)] struct Precalc { inv: Vec, fact: Vec, ifact: Vec, } #[allow(dead_code)] impl Precalc { pub fn new(n: usize) -> Precalc { let mut inv = vec![ModInt::one(); n + 1]; let mut fact = vec![ModInt::one(); n + 1]; let mut ifact = vec![ModInt::one(); n + 1]; for i in 2..(n + 1) { inv[i] = -inv[MOD as usize % i] * ModInt(MOD / i as u32); fact[i] = fact[i - 1] * ModInt(i as u32); ifact[i] = ifact[i - 1] * inv[i]; } Precalc { inv: inv, fact: fact, ifact: ifact, } } pub fn inv(&self, n: usize) -> ModInt { self.inv[n] } pub fn fact(&self, n: usize) -> ModInt { self.fact[n] } pub fn ifact(&self, n: usize) -> ModInt { self.ifact[n] } pub fn comb(&self, n: usize, k: usize) -> ModInt { if k > n { return ModInt::zero(); } self.fact[n] * self.ifact[k] * self.ifact[n - k] } } // ---------- end Precalc ---------- use std::io::Read; // 解説みた // いい感じにDPできるとのことだがどういうことだろう // T が1種類だったら掛け算で計算可能なのでこれを使いそう // Xについてソートしておく // T = 0 の条件をすべて満たしつつT = 1 の条件をk個満たさないものの数を数える // これはすべて <= X という形の条件のみなので掛け算で計算可能 // dp[i][k] : Xが小さい方からi個見て、T=0の条件はすべて満たしつつT=1の条件をk個満たさないものの数とおく // cnt_i : i番目までの条件でT=0のものの数 // とおくと // T_i = 0 のとき // dp[i][k] = dp[i - 1][k] * (X_i - cnt - k) // T_i = 1 のとき // dp[i][k] = dp[i - 1][k - 1] * (X_i - (cnt + k - 1)) + dp[i - 1][k] // とかける // 最後に階乗を掛け合わせて包除 fn run() { let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); let mut it = s.trim().split_whitespace(); let n: usize = it.next().unwrap().parse().unwrap(); let mut cond = vec![]; for _ in 0..n { let t: usize = it.next().unwrap().parse().unwrap(); let x: usize = it.next().unwrap().parse().unwrap(); cond.push((x - t, t)); } cond.sort(); let mut dp = vec![ModInt::zero(); n + 1]; dp[0] = ModInt::one(); let mut cnt = 0; for &(x, t) in cond.iter() { if t == 0 { let mut next = vec![ModInt::zero(); n + 1]; for (j, v) in dp.into_iter().enumerate() { if j + cnt >= x { break; } next[j] = v * ModInt::from(x - j - cnt); } dp = next; cnt += 1; } else { for j in (0..n).rev() { if x <= j + cnt { continue; } let v = dp[j]; dp[j + 1] += v * ModInt::from(x - j - cnt); } } } let mut ans = ModInt::zero(); let pc = Precalc::new(n); let mut sign = ModInt::one(); for (i, v) in dp.into_iter().enumerate().take(n + 1 - cnt) { ans += sign * pc.fact(n - cnt - i) * v; sign = -sign; } println!("{}", ans); } fn main() { run(); }