1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <map>
int n;
int a,b;
std::vector<std::pair<int,int> >prz;
std::vector<int> wyn[500000];
std::set<std::pair<int,int>>cie;
int mod=1e9+7;

long long x;
long long y;

void euk(long long a, long long b)
{
    if(b!=0)
    {
        euk(b, a%b);
        long long pom = y;
        y = x  - a/b*y;
        x = pom;
    }
}
long long euklides(long long a, long long b){
    x=1;
    y=0;
    euk(a,b);
    if(y<0)
        y+=a;
    return y;
}

int main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(NULL);
    cie.emplace(1e9,0);
    std::cin>>n;
    long long wynik=0;
    for(int i=1;i<=n;i++){
        std::cin>>a>>b;
        prz.emplace_back(a,b);
    }
    std::reverse(prz.begin(),prz.end());
    for(int i=0;i<n;i++){
        auto po=cie.upper_bound(std::make_pair(prz[i].first,0));
        auto ko=cie.upper_bound(std::make_pair(prz[i].second,0));

        while(po!=ko){
            wyn[i].emplace_back(po->second);
            for(auto x:wyn[po->second])
                wyn[i].emplace_back(x);
            auto tremove=po;
            po++;
            cie.erase(tremove);

        }
        std::sort(wyn[i].begin(),wyn[i].end());
        auto last = std::unique(wyn[i].begin(), wyn[i].end());
        // v now holds {1 2 3 4 5 x x}, where 'x' is indeterminate
        wyn[i].erase(last, wyn[i].end());
        //std::cout<<"i "<<i<<std::endl;
        //for(auto x:wyn[i])
        //    std::cout<<x<<" ";
        //std::cout<<"\n";
        cie.emplace(prz[i].first,i);
        cie.emplace(prz[i].second,i);
        wynik+=euklides(mod,wyn[i].size()+1);
        wynik%=mod;
        /*if(po->first==ko->first){
            std::cout<<"sierota "<<i<<std::endl;
            poj[i]=-1;
            loj[i]=-1;
            wyn[i]=1;
            cie.emplace(prz[i].first,i);
            cie.emplace(prz[i].second,i);
        }else{
            auto p1=po;
            p1++;
        if(p1==ko){
            std::cout<<"jedynak "<<i<<std::endl;
            wyn[i]=wyn[po->second]+1;
            loj[i]=po->second;
            poj[i]=po->second;
            cie.erase(p1);
            cie.emplace(prz[i].first,i);
            cie.emplace(prz[i].second,i);
        }else{
            while(p1!=ko){
                int le=po->second;
                int pr=p1->second;
                int rle=wyn[le];
                int rpr=wyn[pr];
                std::cout<<le<<" "<<pr<<std::endl;
                while(le!=pr){
                    if(le<pr)
                        pr=loj[pr];
                    else
                        le=poj[le];
                }
                if(le!=-1){
                    wyn=rle+rpr+1;

                    std::cout<<"potomek"<<std::endl;
                }else {
                    std::cout << "niespo" << std::endl;
                }
                auto to_rem=po;
                po++;
                cie.erase(to_rem);
                p1++;

            }
        }
        }*/
    }
    std::cout<<wynik<<std::endl;

}