#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 5e18
#define nl '\n'
const int mod = 1e9+7;
int exp(int a, int b = mod-2){
int p = 1;
while(b > 0){
if(b % 2) p = p * a % mod;
a = a * a % mod;
b /= 2;
}
return p;
}
const int N = 2005;
int dp[N][N];
inline void solve(){
int n;
cin>>n;
vector<pair<int,int>> ab(n+1), lr;
map<int,int> mp;
for(int i=1; i<=n; i++){
int a, b;
cin>>a>>b;
ab[i] = {a, b};
mp[a]++;
mp[b]++;
}
int prev = -1;
lr.push_back({0, 0});
for(auto [x, c] : mp){
if(prev != -1 and prev+1 <= x-1) lr.push_back({prev+1, x-1});
lr.push_back({x, x});
prev = x;
}
int m = lr.size()-1;
for(int i=0; i<=m; i++) dp[0][i] = 1;
int fact[n+1], inv[n+1];
fact[0] = inv[0] = 1;
for(int i=1; i<=n; i++) fact[i] = fact[i-1] * i % mod, inv[i] = exp(fact[i]);
for(int i=1; i<=n; i++){
auto [a, b] = ab[i];
dp[i][0] = 1;
for(int j=1; j<=m; j++){
auto [l, r] = lr[j];
int len = r-l+1;
dp[i][j] = dp[i][j-1];
int cnt = 0, p = 1;
for(int k=i; k>0; k--){
auto [a, b] = ab[k];
if(l < a or r > b) continue;
cnt++;
p = p * (len + cnt - 1) % mod;
dp[i][j] += p * inv[cnt] % mod * dp[k-1][j-1];
dp[i][j] %= mod;
}
}
}
cout<<(dp[n][m]-1+mod) % mod<<nl;
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);cout.tie(NULL);
int t = 1;
//cin>>t;
while(t--) solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |