线段树优化dp的常见套路题，就是先按某个参数排序，然后按这个下标建立线段树，再去优化dp
本题由于要维护两个数据：最小值和对应的方案数，所以用线段树区间合并
/*
dp[i]表示第i个套娃作为最内层的最小浪费空间
dp[i]=min(dp[j])+out[i]-in[i];
那么按照out排序后按下标建立线段树，节点维护的是二元组(区间最小值，这个最小值对应的方案数）
求dp[i]时二分找到out[j]<=in[i]的区间[1,pos],然后线段树里查询再更新 处理方案数，线段树向上合并时，只保留值最小的那个节点信息即可，如果值相同，那么将方案数合并即可
初始值：如果一个娃外面套任何东西，那么这个娃的方案数设为1即*/ #include<bits/stdc++.h>
using namespace std;
#define N 200005
#define ll long long
#define mod 1000000007 inline ll f(ll a,ll b){
ll res=a+b;
if(res>mod)res-=mod;
return res;
} struct Node{ll out,in;}a[N];
bool operator<(Node a,Node b){return a.in<b.in;}
ll n,dp[N],x[N]; #define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
struct Seg {
ll val,num;
Seg(){}
Seg(ll val,ll num):val(val),num(num){}
}seg[N<<];
Seg merge(Seg A,Seg B){
if(A.val<B.val)return A;
if(A.val>B.val)return B;
Seg res;
res.val=A.val;
res.num=(A.num+B.num)%mod;
return res;
}
void build(int l,int r,int rt){
seg[rt].num=;seg[rt].val=0x3f3f3f3f3f3f3f3f;
if(l==r)return;
int m=l+r>>;
build(lson);build(rson);
}
void update(int pos,ll val,ll num,int l,int r,int rt){
if(l==r){seg[rt].num=num;seg[rt].val=val;return;}
int m=l+r>>;
if(pos<=m)update(pos,val,num,lson);
else update(pos,val,num,rson);
seg[rt]=merge(seg[rt<<],seg[rt<<|]);
}
Seg query(int L,int R,int l,int r,int rt){
if(L<=l && R>=r)return seg[rt];
int m=l+r>>;
Seg res;
res.val=0x3f3f3f3f3f3f3f3f;
if(L<=m)res=merge(res,query(L,R,lson));
if(R>m)res=merge(res,query(L,R,rson));
return res;
} void debug(int l,int r,int rt){
cout<<l<<" "<<r<<" "<<seg[rt].num<<" "<<seg[rt].val<<"\n";
if(l==r)return;
int m=l+r>>;
debug(lson);debug(rson);
} int main(){
cin>>n;
for(int i=;i<=n;i++){
cin>>a[i].out>>a[i].in;
x[i]=a[i].in;
}
sort(a+,a++n);sort(x+,x++n); build(,n,);
for(int i=n;i>=;i--){
int pos=lower_bound(x+,x++n,a[i].out)-x;
if(pos>n){//外面套不了娃
update(i,a[i].in,,,n,);
}
else {
Seg res=query(pos,n,,n,);
//cout<<res.val<<" "<<res.num<<'\n';
update(i,res.val-(a[i].out-a[i].in),res.num,,n,);
//cout<<res.val<<" "<<res.num<<'\n';
}
//debug(1,n,1);
}
Seg res=query(,n,,n,);
cout<<res.num;
}