#include<bits/stdc++.h>
using namespace std;
// #include<atcoder/all>
// using namespace atcoder;
// using mint=atcoder::modint998244353;
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define int long long
#define rep(i,n) for(int i=0;i<(n);i++)
#define rng(i,l,r) for(int i=(l);i<(r);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define rrng(i,l,r) for(int i=(r)-1;i>=(l);i--)
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
struct fast_io{fast_io(){cin.tie(nullptr)->sync_with_stdio(false);}}_;
template<long long mod,long long MAX_N>
struct factional_prime{
long long inv_[MAX_N+1];
long long fac_[MAX_N+1];
long long fac_inv_[MAX_N+1];
factional_prime(){
inv_[0]=0;inv_[1]=fac_[0]=fac_[1]=fac_inv_[0]=fac_inv_[1]=1;
for(long long i=2;i<=MAX_N;i++){
inv_[i]=((mod-mod/i)*inv_[mod%i])%mod;
fac_[i]=(fac_[i-1]*i)%mod;
fac_inv_[i]=(fac_inv_[i-1]*inv_[i])%mod;
}
}
long long inv(long long n){
if(n<0)return 0;
return inv_[n];
}
long long fac(long long n){
if(n<0)return 0;
return fac_[n];
}
long long finv(long long n){
if(n<0)return 0;
return fac_inv_[n];
}
long long nCr(long long n,long long r){
if(n<r||n<0||r<0)return 0;
return ((fac_[n]*fac_inv_[n-r])%mod*fac_inv_[r])%mod;
}
long long nPr(long long n,long long r){
if(n<r||n<0||r<0)return 0;
return (fac_[n]*fac_inv_[n-r])%mod;
}
};
factional_prime<998244353,5000000> fp;
signed main(){
int N;cin>>N;
vector<int> A(N),B(N);
rep(i,N)cin>>A[i]>>B[i],B[i]++;
vector<int> v=A;v.insert(v.end(),all(B));
sort(all(v));v.erase(unique(all(v)),v.end());
int m=v.size()-1;
const int mod=1000000007;
vector<vector<int>> dp(m,vector<int>(N+1));
vector<vector<int>> bi(m,vector<int>(N+1));
rep(i,m){
bi[i][0]=1;
rep(j,N){
bi[i][j+1]=bi[i][j]*(v[i+1]-v[i]-j)*fp.inv(j+1)%mod;
}
}
rep(i,N){
vector<vector<int>> ndp(m,vector<int>(N+1));
int sum=1;
rep(j,m){
if(A[i]<=v[j]&&v[j+1]<=B[i]){
ndp[j][1]+=sum;
ndp[j][1]%=mod;
}
rep(k,i+1){
if(A[i]<=v[j]&&v[j+1]<=B[i]){
ndp[j][k+1]+=dp[j][k];
ndp[j][k+1]%=mod;
}
ndp[j][k]+=dp[j][k];
ndp[j][k]%=mod;
sum+=dp[j][k]*bi[j][k];
sum%=mod;
}
}
swap(dp,ndp);
// cout<<"dp : "<<endl;
// rep(j,m){
// cout<<j<<" : ";
// for(auto&&e:dp[j])cout<<e<<" ";cout<<endl;
// }
}
int ans=0;
rep(j,m){
rep(k,N+1){
ans+=dp[j][k]*bi[j][k];
ans%=mod;
}
}
cout<<ans<<endl;
}
# | 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... |