#include<bits/stdc++.h>
using namespace std;
const int MAXN=1024;
const long long mod=1e9+7;
long long dp[MAXN][MAXN],pre[MAXN][MAXN],sum[MAXN],val[MAXN],L[MAXN],R[MAXN],inv[MAXN];
long long poww(long long n,long long m)
{
long long res=n,ans=1;
while(m)
{
if(m&1) ans=ans*res%mod;
res=res*res%mod,m/=2;
}
return ans;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
int cnt=0;
for(int i=1;i<=n;i++)
{
cin>>L[i]>>R[i];
val[++cnt]=L[i],val[++cnt]=R[i]+1;
}
for(int i=1;i<=cnt;i++) inv[i]=poww(i,mod-2);
sort(val+1,val+cnt+1);
dp[0][1]=1;
for(int i=1;i<=n;i++)
{
int l=lower_bound(val+1,val+cnt+1,L[i])-val;
int r=lower_bound(val+1,val+cnt+1,R[i]+1)-val-1;
for(int j=0;j<cnt;j++)
{
sum[j]=0;
for(int k=1;k<=n;k++) pre[j][k]=dp[j][k],sum[j]=(sum[j]+pre[j][k])%mod;
if(j) sum[j]=(sum[j]+sum[j-1])%mod;
}
for(int j=l;j<=r;j++) for(int k=1;k<=n;k++) dp[j][k]=(dp[j][k]+sum[j-1]*(val[j+1]-val[j])*(k==1)+pre[j][k-1]*max(0LL,val[j+1]-val[j]-k+1)%mod*inv[k])%mod;
}
long long ans=0;
for(int j=0;j<cnt;j++) for(int k=1;k<=n;k++) ans=(ans+dp[j][k])%mod;
cout<<(ans-1+mod)%mod;
}
| # | 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... |