#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,mod=1000000007LL,sub1,f[509],DPI[509],pas,li,dp[1509],dpp[1509],dp2[1509][509],dpp2[1509][509],fct[509],C[1509][509],len[1509],wu[1509];
pair <long long, long long> p[509],l[5009];
map <long long, long long> m,n;
map <long long, long long>::iterator it,tt;
long long xar(long long q, long long w){
if(w==0) return 1LL;
long long qw=xar(q,w/2);
if(w%2==0) return (qw*qw)%mod; else return ((qw*qw)%mod*q)%mod;
}
long long dv(long long q, long long w){
return (q*xar(w,mod-2))%mod;
}
int main(){
ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>a;
for(i=1; i<=a; i++){
cin>>p[i].first>>p[i].second;
if(p[i].first!=p[i].second){
sub1=1;
}
}
if(sub1==0){
DPI[a]=1;
for(i=a-1; i>=1; i--){
for(j=i+1; j<=a; j++){
if(p[j].first>p[i].first){
DPI[i]+=DPI[j];
if(DPI[i]>=mod) DPI[i]-=mod;
}
}
DPI[i]++;
if(DPI[i]>=mod) DPI[i]-=mod;
}
for(i=1; i<=a; i++){
pas+=DPI[i];
if(pas>=mod) pas-=mod;
}
cout<<pas;
return 0;
}
for(i=1; i<=a; i++){
m[p[i].first]=1;
m[p[i].second]=1;
}
for(it=m.begin(); it!=m.end(); it++){
li++;
l[li].first=(*it).first;
l[li].second=(*it).first;
tt=it;tt++;
if(tt!=m.end()&&(*it).first+1<=(*tt).first-1){
li++;
l[li].first=(*it).first+1;
l[li].second=(*tt).first-1;
}
}
/*cout<<li<<endl;
for(i=1; i<=li; i++){
cout<<l[i].first<<" "<<l[i].second<<endl;
}*/
for(i=1; i<=li; i++){
n[l[i].first]=l[i].second;
}
for(i=1; i<=li; i++){
len[i]=l[i].second-l[i].first+1;
C[i][0]=1;
for(j=1; j<=min(a,len[i]); j++){
zx=dv(len[i]-j+1,j);
C[i][j]=(C[i][j-1]*zx)%mod;
//cout<<len[i]<<" "<<j<<" "<<C[i][j]<<endl;
}
}
for(ii=a; ii>=1; ii--){
for(i=0; i<=li+2; i++){
dpp[i]=dp[i];
for(j=0; j<=a+2; j++){
dpp2[i][j]=dp2[i][j];
}
}
for(i=1; i<=li; i++){
if(l[i].second<p[ii].first||l[i].first>p[ii].second) continue;
wu[i]++;
for(j=i+1; j<=li; j++){
/*dpp[i]+=dp[j]*len[i];
dpp[i]%=mod;*/
dpp2[i][1]+=dp[j];
if(dpp2[i][1]>=mod) dpp2[i][1]-=mod;
}
dpp2[i][1]++;
if(dpp2[i][1]>=mod) dpp2[i][1]-=mod;
for(j=1; j<wu[i]; j++){
dpp2[i][j+1]+=dp2[i][j];
if(dpp2[i][j+1]>=mod) dpp2[i][j+1]-=mod;
}
dpp[i]=0;
for(j=1; j<=wu[i]; j++){
//if(j>len[i]) break;
dpp[i]+=dpp2[i][j]*C[i][j];
//if(dpp[i]>=mod) dpp[i]-=mod;
dpp[i]%=mod;
}
}
for(i=1; i<=li; i++){
dp[i]=dpp[i];
for(j=0; j<=a+2; j++){
dp2[i][j]=dpp2[i][j];
}
}
/* for(i=1; i<=li; i++) cout<<dp[i]<<" ";
cout<<endl;*/
}
//cout<<dp2[2][1]<<endl;
pas=0;
for(i=1; i<=li; i++){
pas+=dp[i];
if(pas>=mod) pas-=mod;
}
cout<<pas;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
21 |
Runtime error |
25 ms |
25356 KB |
Execution killed with signal 11 |
22 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
33 ms |
5068 KB |
Output is correct |
2 |
Correct |
29 ms |
5168 KB |
Output is correct |
3 |
Correct |
30 ms |
5144 KB |
Output is correct |
4 |
Correct |
32 ms |
5068 KB |
Output is correct |
5 |
Correct |
29 ms |
5068 KB |
Output is correct |
6 |
Correct |
33 ms |
5068 KB |
Output is correct |
7 |
Correct |
34 ms |
5144 KB |
Output is correct |
8 |
Correct |
33 ms |
5064 KB |
Output is correct |
9 |
Correct |
33 ms |
5068 KB |
Output is correct |
10 |
Correct |
33 ms |
5164 KB |
Output is correct |
11 |
Correct |
28 ms |
5076 KB |
Output is correct |
12 |
Correct |
26 ms |
5112 KB |
Output is correct |
13 |
Correct |
27 ms |
5068 KB |
Output is correct |
14 |
Correct |
29 ms |
5156 KB |
Output is correct |
15 |
Correct |
27 ms |
5148 KB |
Output is correct |
16 |
Correct |
11 ms |
2448 KB |
Output is correct |
17 |
Correct |
11 ms |
2380 KB |
Output is correct |
18 |
Correct |
11 ms |
2380 KB |
Output is correct |
19 |
Correct |
10 ms |
2380 KB |
Output is correct |
20 |
Correct |
11 ms |
2536 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
21 |
Runtime error |
25 ms |
25356 KB |
Execution killed with signal 11 |
22 |
Halted |
0 ms |
0 KB |
- |