Problem:


Score : 1200 points

Problem Statement

Takahashi is an expert of Clone Jutsu, a secret art that creates copies of his body.

On a number line, there are N copies of Takahashi, numbered 1 through N.
The i-th copy is located at position X_i and starts walking with velocity V_i in the positive direction at time 0.

Kenus is a master of Transformation Jutsu, and not only can he change into a person other than himself, but he can also transform another person into someone else.

Kenus can select some of the copies of Takahashi at time 0, and transform them into copies of Aoki, another Ninja.
The walking velocity of a copy does not change when it transforms.
From then on, whenever a copy of Takahashi and a copy of Aoki are at the same coordinate, that copy of Takahashi transforms into a copy of Aoki.

Among the 2^N ways to transform some copies of Takahashi into copies of Aoki at time 0, in how many ways will all the copies of Takahashi become copies of Aoki after a sufficiently long time?
Find the count modulo 10^9+7.

Constraints

1 ≤ N ≤ 200000

1 ≤ X_i,V_i ≤ 10^9(1 ≤ i ≤ N)

X_i and V_i are integers.

All X_i are distinct.

All V_i are distinct.

Input

The input is given from Standard Input in the following format:

N
X_1 V_1
:
X_N V_N

Output

Print the number of the ways that cause all the copies of Takahashi to turn into copies of Aoki after a sufficiently long time, modulo 10^9+7.

Sample Input 1

3
2 5
6 1
3 7

Sample Output 1

6

All copies of Takahashi will turn into copies of Aoki after a sufficiently long time if Kenus transforms one of the following sets of copies of Takahashi into copies of Aoki: (2), (3), (1,2), (1,3), (2,3) and (1,2,3).

Sample Input 2

4
3 7
2 9
8 16
10 8

Sample Output 2

9



Sample input:
3
2 5
6 1
3 7


Sample output:
6

Submission status: Wrong Answer

Solution code:
class BIT():
    def __init__(self,n,mod):
        self.BIT=[0]*(n+1)
        self.num=n
        self.mod=mod

    def query(self,idx):
        res_sum = 0
        mod=self.mod
        while idx > 0:
            res_sum += self.BIT[idx]
            res_sum%=mod
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def update(self,idx,x):
        mod=self.mod
        while idx <= self.num:
            self.BIT[idx] += x
            self.BIT[idx]%=mod
            idx += idx&(-idx)
        return

import sys,bisect

input=sys.stdin.readline

mod=10**9+7
inv=pow(2,mod-2,mod)

N=int(input())
taka=[tuple(map(int,input().split())) for i in range(N)]
taka.sort()

V=[0]+[taka[i][1] for i in range(N)]+[10**15]
cummin=[V[i] for i in range(N+2)]
for i in range(N,-1,-1):
    cummin[i]=min(cummin[i],cummin[i+1])
cummax=[V[i] for i in range(N+2)]
for i in range(1,N+2):
    cummax[i]=max(cummax[i],cummax[i-1])

const=[]
for i in range(1,N+1):
    R=bisect.bisect_right(cummin,V[i])-1
    L=bisect.bisect_left(cummax,V[i])
    const.append((L,R))


Lconst=[(i,10**15) for i in range(N+1)]
for L,R in const:
    pL,pR=Lconst[L]
    Lconst[L]=(L,min(R,pR))

_const=[]
for i in range(1,N+1):
    L,R=Lconst[i]
    if R!=10**15:
        _const.append((L,R))

const=[]
for L,R in _const:
    while const and const[-1][1]>=R:
        const.pop()
    const.append((L,R))


M=len(const)
const=[(-10**15,0)]+const
Rconst=[const[i][1] for i in range(M+1)]
B=BIT(M,mod)
dp=[1]*(M+1)
for i in range(1,M+1):
    L,R=const[i]
    id=bisect.bisect_left(Rconst,L)
    res=(B.query(i-1)-B.query(id-1))%mod
    l,r=const[id]
    res+=dp[id-1]*(pow(2,r-L+1,mod)-1)*pow(2,L-l,mod)%mod
    res%=mod
    dp[i]=res
    if i!=M:
        nR=Rconst[i+1]
        add=dp[i]*(pow(2,nR-R,mod)-1)%mod
        add%=mod
        B.update(i,add)

cnt=0
data=[0]*(N+2)
for i in range(1,M+1):
    L,R=const[i]
    data[L]+=1
    data[R+1]+=-1
for i in range(1,N+2):
    data[i]+=data[i-1]
for i in range(1,N+1):
    if data[i]==0:
        cnt+=1
ans=pow(2,cnt,mod)*dp[M]
ans%=mod
print(ans)

Submission status: Wrong Answer

Solution code:
class BIT():
    def __init__(self,n,mod):
        self.BIT=[0]*(n+1)
        self.num=n
        self.mod=mod

    def query(self,idx):
        res_sum = 0
        mod=self.mod
        while idx > 0:
            res_sum += self.BIT[idx]
            res_sum%=mod
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def update(self,idx,x):
        mod=self.mod
        while idx <= self.num:
            self.BIT[idx] += x
            self.BIT[idx]%=mod
            idx += idx&(-idx)
        return

import sys,bisect

input=sys.stdin.readline

mod=10*9+7
inv=pow(2,mod-2,mod)

N=int(input())
taka=[tuple(map(int,input().split())) for i in range(N)]
taka.sort()

V=[0]+[taka[i][1] for i in range(N)]+[10**15]
cummin=[V[i] for i in range(N+2)]
for i in range(N,-1,-1):
    cummin[i]=min(cummin[i],cummin[i+1])
cummax=[V[i] for i in range(N+2)]
for i in range(1,N+2):
    cummax[i]=max(cummax[i],cummax[i-1])

const=[]
for i in range(1,N+1):
    R=bisect.bisect_right(cummin,V[i])-1
    L=bisect.bisect_left(cummax,V[i])
    const.append((L,R))


Lconst=[(i,10**15) for i in range(N+1)]
for L,R in const:
    pL,pR=Lconst[L]
    Lconst[L]=(L,min(R,pR))

_const=[]
for i in range(1,N+1):
    L,R=Lconst[i]
    if R!=10**15:
        _const.append((L,R))

const=[]
for L,R in _const:
    while const and const[-1][1]>=R:
        const.pop()
    const.append((L,R))

M=len(const)
const=[(-10**15,0)]+const
Rconst=[const[i][1] for i in range(M+1)]
B=BIT(M,mod)
dp=[1]*(M+1)
for i in range(1,M+1):
    L,R=const[i]
    id=bisect.bisect_left(Rconst,L)
    res=(B.query(i-1)-B.query(id-1))%mod
    l,r=const[id]
    res+=dp[id-1]*(pow(2,r-L+1,mod)-1)*pow(2,L-l,mod)%mod
    res%=mod
    dp[i]=res
    if i!=M:
        nR=Rconst[i+1]
        add=dp[i]*(pow(2,nR-R,mod)-1)%mod
        add%=mod
        B.update(i,add)

cnt=0
data=[0]*(N+2)
for i in range(1,M+1):
    L,R=const[i]
    data[L]+=1
    data[R+1]+=-1
for i in range(1,N+2):
    data[i]+=data[i-1]
for i in range(1,N+1):
    if data[i]==0:
        cnt+=1

ans=pow(2,cnt,mod)*dp[M]
ans%=mod
print(ans)

Submission status: Wrong Answer

Solution code:
class BIT():
    def __init__(self,n,mod):
        self.BIT=[0]*(n+1)
        self.num=n
        self.mod=mod

    def query(self,idx):
        res_sum = 0
        mod=self.mod
        while idx > 0:
            res_sum += self.BIT[idx]
            res_sum%=mod
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def update(self,idx,x):
        mod=self.mod
        while idx <= self.num:
            self.BIT[idx] += x
            self.BIT[idx]%=mod
            idx += idx&(-idx)
        return

import sys,bisect

input=sys.stdin.readline

mod=10*9+7
inv=pow(2,mod-2,mod)

N=int(input())
taka=[tuple(map(int,input().split())) for i in range(N)]
taka.sort()

V=[0]+[taka[i][1] for i in range(N)]+[10**15]
cummin=[V[i] for i in range(N+2)]
for i in range(N,-1,-1):
    cummin[i]=min(cummin[i],cummin[i+1])
cummax=[V[i] for i in range(N+2)]
for i in range(1,N+2):
    cummax[i]=max(cummax[i],cummax[i-1])

const=[]
for i in range(1,N+1):
    R=bisect.bisect_right(cummin,V[i])-1
    L=bisect.bisect_left(cummax,V[i])
    const.append((L,R))


Lconst=[(i,10**15) for i in range(N+1)]
for L,R in const:
    pL,pR=Lconst[L]
    Lconst[L]=(L,min(R,pR))

_const=[]
for i in range(1,N+1):
    L,R=Lconst[i]
    if R!=10**15:
        _const.append((L,R))

const=[]
for L,R in _const:
    while const and const[-1][1]>=R:
        const.pop()
    const.append((L,R))

M=len(const)
const=[(-10**15,0)]+const
Rconst=[const[i][1] for i in range(M+1)]
B=BIT(M,mod)
dp=[1]*(M+1)
for i in range(1,M+1):
    L,R=const[i]
    id=bisect.bisect_left(Rconst,L)
    res=(B.query(i-1)-B.query(id-1))%mod
    r=Rconst[id]
    res+=dp[id-1]*(pow(2,r-L+1,mod)-1)*pow(2,L-Rconst[id-1]-1,mod)%mod
    res%=mod
    dp[i]=res
    if i!=M:
        nR=Rconst[i+1]
        add=dp[i]*(pow(2,nR-R,mod)-1)%mod
        add%=mod
        B.update(i,add)

cnt=0
data=[0]*(N+2)
for i in range(1,M+1):
    L,R=const[i]
    data[L]+=1
    data[R+1]+=-1
for i in range(1,N+2):
    data[i]+=data[i-1]
for i in range(1,N+1):
    if data[i]==0:
        cnt+=1

ans=pow(2,cnt,mod)*dp[M]
ans%=mod
print(ans)

Submission status: Wrong Answer

Solution code:
class BIT():
    def __init__(self,n,mod):
        self.BIT=[0]*(n+1)
        self.num=n
        self.mod=mod

    def query(self,idx):
        res_sum = 0
        mod=self.mod
        while idx > 0:
            res_sum += self.BIT[idx]
            res_sum%=mod
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def update(self,idx,x):
        mod=self.mod
        while idx <= self.num:
            self.BIT[idx] += x
            self.BIT[idx]%=mod
            idx += idx&(-idx)
        return

import sys,bisect

input=sys.stdin.readline

mod=10*9+7
inv=pow(2,mod-2,mod)

N=int(input())
taka=[tuple(map(int,input().split())) for i in range(N)]
taka.sort()

V=[0]+[taka[i][1] for i in range(N)]+[10**15]
cummin=[V[i] for i in range(N+2)]
for i in range(N,-1,-1):
    cummin[i]=min(cummin[i],cummin[i+1])
cummax=[V[i] for i in range(N+2)]
for i in range(1,N+2):
    cummax[i]=max(cummax[i],cummax[i-1])

const=[]
for i in range(1,N+1):
    R=bisect.bisect_right(cummin,V[i])-1
    L=bisect.bisect_left(cummax,V[i])
    const.append((L,R))


Lconst=[(i,10**15) for i in range(N+1)]
for L,R in const:
    pL,pR=Lconst[L]
    Lconst[L]=(L,min(R,pR))

_const=[]
for i in range(1,N+1):
    L,R=Lconst[i]
    if R!=10**15:
        _const.append((L,R))

const=[]
for L,R in _const:
    while const and const[-1][1]>=R:
        const.pop()
    const.append((L,R))

M=len(const)
const=[(-10**15,-10**15)]+const
Rconst=[const[i][1] for i in range(M+1)]
B=BIT(M,mod)
dp=[1]*(M+1)
for i in range(1,M+1):
    L,R=const[i]
    id=bisect.bisect_left(Rconst,L)
    res=(B.query(i-1)-B.query(id-1))*pow(inv,L-1,mod)%mod
    r=Rconst[id]
    res+=dp[id-1]*(pow(2,r-L+1,mod)-1)%mod
    res%=mod
    dp[i]=res
    if i!=M:
        nR=Rconst[i+1]
        add=dp[i]*(pow(2,nR-R,mod)-1)*pow(2,R,mod)%mod
        add%=mod
        B.update(i,add)

cnt=0
data=[0]*(N+2)
for i in range(1,M+1):
    L,R=const[i]
    data[L]+=1
    data[R+1]+=-1
for i in range(1,N+2):
    data[i]+=data[i-1]
for i in range(1,N+1):
    if data[i]==0:
        cnt+=1

ans=pow(2,cnt,mod)*dp[M]
ans%=mod
print(ans)

Submission status: Wrong Answer

Solution code:
class BIT():
    def __init__(self,n,mod):
        self.BIT=[0]*(n+1)
        self.num=n
        self.mod=mod

    def query(self,idx):
        res_sum = 0
        mod=self.mod
        while idx > 0:
            res_sum += self.BIT[idx]
            res_sum%=mod
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def update(self,idx,x):
        mod=self.mod
        while idx <= self.num:
            self.BIT[idx] += x
            self.BIT[idx]%=mod
            idx += idx&(-idx)
        return

import sys,bisect

input=sys.stdin.readline

mod=10*9+7
inv=pow(2,mod-2,mod)

N=int(input())
taka=[tuple(map(int,input().split())) for i in range(N)]
taka.sort()

V=[0]+[taka[i][1] for i in range(N)]+[10**15]
cummin=[V[i] for i in range(N+2)]
for i in range(N,-1,-1):
    cummin[i]=min(cummin[i],cummin[i+1])
cummax=[V[i] for i in range(N+2)]
for i in range(1,N+2):
    cummax[i]=max(cummax[i],cummax[i-1])

const=[]
for i in range(1,N+1):
    R=bisect.bisect_right(cummin,V[i])-1
    L=bisect.bisect_left(cummax,V[i])
    const.append((L,R))


Lconst=[(i,10**15) for i in range(N+1)]
for L,R in const:
    pL,pR=Lconst[L]
    Lconst[L]=(L,min(R,pR))

_const=[]
for i in range(1,N+1):
    L,R=Lconst[i]
    if R!=10**15:
        _const.append((L,R))

const=[]
for L,R in _const:
    while const and const[-1][1]>=R:
        const.pop()
    const.append((L,R))

M=len(const)
const=[(-10**15,-10**15)]+const
Rconst=[const[i][1] for i in range(M+1)]
B=BIT(M,mod)
dp=[1]*(M+1)
for i in range(1,M+1):
    L,R=const[i]
    id=bisect.bisect_left(Rconst,L)
    res=(B.query(i-1)-B.query(id-1))*pow(inv,L-1,mod)%mod
    R=Rconst[id]
    res+=dp[id-1]*(pow(2,R-L+1,mod)-1)%mod
    res%=mod
    dp[i]=res
    if i!=M:
        nR=Rconst[i+1]
        add=dp[i]*(pow(2,nR-R,mod)-1)*pow(2,R,mod)%mod
        add%=mod
        B.update(i,add)

cnt=0
data=[0]*(N+2)
for i in range(1,M+1):
    L,R=const[i]
    data[L]+=1
    data[R+1]+=-1
for i in range(1,N+2):
    data[i]+=data[i-1]
for i in range(1,N+1):
    if data[i]==0:
        cnt+=1

ans=pow(2,cnt,mod)*dp[M]
ans%=mod
print(ans)

Submission status: Wrong Answer

Solution code:
class BIT():
    def __init__(self,n,mod):
        self.BIT=[0]*(n+1)
        self.num=n
        self.mod=mod

    def query(self,idx):
        res_sum = 0
        mod=self.mod
        while idx > 0:
            res_sum += self.BIT[idx]
            res_sum%=mod
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def update(self,idx,x):
        mod=self.mod
        while idx <= self.num:
            self.BIT[idx] += x
            self.BIT[idx]%=mod
            idx += idx&(-idx)
        return

import sys,bisect

input=sys.stdin.readline

mod=10*9+7

N=int(input())
taka=[tuple(map(int,input().split())) for i in range(N)]
taka.sort()

V=[0]+[taka[i][1] for i in range(N)]+[10**15]
cummin=[V[i] for i in range(N+2)]
for i in range(N,-1,-1):
    cummin[i]=min(cummin[i],cummin[i+1])
cummax=[V[i] for i in range(N+2)]
for i in range(1,N+2):
    cummax[i]=max(cummax[i],cummax[i-1])

const=[]
for i in range(1,N+1):
    R=bisect.bisect_right(cummin,V[i])-1
    L=bisect.bisect_left(cummax,V[i])
    const.append((L,R))


Lconst=[(i,10**15) for i in range(N+1)]
for L,R in const:
    pL,pR=Lconst[L]
    Lconst[L]=(L,min(R,pR))

_const=[]
for i in range(1,N+1):
    L,R=Lconst[i]
    if R!=10**15:
        _const.append((L,R))

const=[]
for L,R in _const:
    while const and const[-1][1]>=R:
        const.pop()
    const.append((L,R))

M=len(const)
const=[(-10**15,-10**15)]+const
Rconst=[const[i][1] for i in range(M+1)]
B=BIT(M,mod)
dp=[1]*(M+1)
for i in range(1,M+1):
    L,R=const[i]
    id=bisect.bisect_left(Rconst,L)
    res=(B.query(i-1)-B.query(id-1))%mod
    R=Rconst[id]
    res+=dp[id-1]*(pow(2,R-L+1,mod)-1)%mod
    res%=mod
    dp[i]=res
    if i!=M:
        nR=Rconst[i+1]
        add=dp[i]*(pow(2,nR-R,mod)-1)*pow(2,nR-L+1,mod)%mod
        add%=mod
        B.update(i,add)

cnt=0
data=[0]*(N+2)
for i in range(1,M+1):
    L,R=const[i]
    data[L]+=1
    data[R+1]+=-1
for i in range(1,N+2):
    data[i]+=data[i-1]
for i in range(1,N+1):
    if data[i]==0:
        cnt+=1

ans=pow(2,cnt,mod)*dp[M]
ans%=mod
print(ans)

Submission status: Wrong Answer

Solution code:
class BIT():
    def __init__(self,n,mod):
        self.BIT=[0]*(n+1)
        self.num=n
        self.mod=mod

    def query(self,idx):
        res_sum = 0
        mod=self.mod
        while idx > 0:
            res_sum += self.BIT[idx]
            res_sum%=mod
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def update(self,idx,x):
        mod=self.mod
        while idx <= self.num:
            self.BIT[idx] += x
            self.BIT[idx]%=mod
            idx += idx&(-idx)
        return

import sys,bisect

input=sys.stdin.readline

mod=10*9+7

N=int(input())
taka=[tuple(map(int,input().split())) for i in range(N)]
taka.sort()

V=[0]+[taka[i][1] for i in range(N)]+[10**15]
cummin=[V[i] for i in range(N+2)]
for i in range(N,-1,-1):
    cummin[i]=min(cummin[i],cummin[i+1])
cummax=[V[i] for i in range(N+2)]
for i in range(1,N+2):
    cummax[i]=max(cummax[i],cummax[i-1])

const=[]
for i in range(1,N+1):
    R=bisect.bisect_right(cummin,V[i])-1
    L=bisect.bisect_left(cummax,V[i])
    const.append((L,R))


Lconst=[(i,10**15) for i in range(N+1)]
for L,R in const:
    pL,pR=Lconst[L]
    Lconst[L]=(L,min(R,pR))


Rconst=[(-1,i) for i in range(N+1)]
for i in range(1,N+1):
    L,R=Lconst[i]
    if R!=10**15:
        pL,pR=Rconst[R]
        Rconst[R]=(max(pL,L),R)


_const=[]
for i in range(1,N+1):
    L,R=Rconst[i]
    if L!=-1:
        _const.append((L,R))

_const.sort()
const=[]
for L,R in _const:
    while const and const[-1][1]>=R:
        const.pop()
    const.append((L,R))

M=len(const)
const=[(-10**15,-10**15)]+const
Rconst=[const[i][1] for i in range(M+1)]
B=BIT(M,mod)
dp=[1]*(M+1)
for i in range(1,M+1):
    L,R=const[i]
    id=bisect.bisect_left(Rconst,L)
    res=(B.query(i-1)-B.query(id-1))%mod
    R=Rconst[id]
    res+=dp[id-1]*(pow(2,R-L+1,mod)-1)%mod
    res%=mod
    dp[i]=res
    if i!=M:
        nR=Rconst[i+1]
        add=dp[i]*(pow(2,nR-R,mod)-1)%mod
        add%=mod
        B.update(i,add)

cnt=0
data=[0]*(N+2)
for i in range(1,M+1):
    L,R=const[i]
    data[L]+=1
    data[R+1]+=-1
for i in range(1,N+2):
    data[i]+=data[i-1]
for i in range(1,N+1):
    if data[i]==0:
        cnt+=1

ans=pow(2,cnt,mod)*dp[M]
ans%=mod
print(ans)

Submission status: Wrong Answer

Solution code:
class BIT():
    def __init__(self,n,mod):
        self.BIT=[0]*(n+1)
        self.num=n
        self.mod=mod

    def query(self,idx):
        res_sum = 0
        mod=self.mod
        while idx > 0:
            res_sum += self.BIT[idx]
            res_sum%=mod
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def update(self,idx,x):
        mod=self.mod
        while idx <= self.num:
            self.BIT[idx] += x
            self.BIT[idx]%=mod
            idx += idx&(-idx)
        return

import sys,bisect

input=sys.stdin.readline

mod=10*9+7

N=int(input())
taka=[tuple(map(int,input().split())) for i in range(N)]
taka.sort()

V=[0]+[taka[i][1] for i in range(N)]+[10**15]
cummin=[V[i] for i in range(N+2)]
for i in range(N,-1,-1):
    cummin[i]=min(cummin[i],cummin[i+1])
cummax=[V[i] for i in range(N+2)]
for i in range(1,N+2):
    cummax[i]=max(cummax[i],cummax[i-1])

const=[]
for i in range(1,N+1):
    R=bisect.bisect_right(cummin,V[i])-1
    L=bisect.bisect_left(cummax,V[i])
    const.append((L,R))


Lconst=[(i,10**15) for i in range(N+1)]
for L,R in const:
    pL,pR=Lconst[L]
    Lconst[L]=(L,min(R,pR))


Rconst=[(-1,i) for i in range(N+1)]
for i in range(1,N+1):
    L,R=Lconst[i]
    if R!=10**15:
        pL,pR=Rconst[R]
        Rconst[R]=(max(pL,L),R)


_const=[]
for i in range(1,N+1):
    L,R=Rconst[i]
    if L!=-1:
        _const.append((L,R))

_const.sort()
const=[]
for L,R in _const:
    while const and const[-1][1]>=R:
        cosnt.pop()
    const.append((L,R))

M=len(const)
const=[(-10**15,-10**15)]+const
Rconst=[const[i][1] for i in range(M+1)]
B=BIT(M,mod)
dp=[1]*(M+1)
for i in range(1,M+1):
    L,R=const[i]
    id=bisect.bisect_left(Rconst,L)
    res=(B.query(i-1)-B.query(id-1))%mod
    R=Rconst[id]
    res+=dp[id-1]*(pow(2,R-L+1,mod)-1)%mod
    res%=mod
    dp[i]=res
    if i!=M:
        nR=Rconst[i+1]
        add=dp[i]*(pow(2,nR-R,mod)-1)%mod
        add%=mod
        B.update(i,add)

cnt=0
data=[0]*(N+2)
for i in range(1,M+1):
    L,R=const[i]
    data[L]+=1
    data[R+1]+=-1
for i in range(1,N+2):
    data[i]+=data[i-1]
for i in range(1,N+1):
    if data[i]==0:
        cnt+=1

ans=pow(2,cnt,mod)*dp[M]
ans%=mod
print(ans)

Submission status: Wrong Answer

Solution code:
class BIT():
    def __init__(self,n,mod):
        self.BIT=[0]*(n+1)
        self.num=n
        self.mod=mod

    def query(self,idx):
        res_sum = 0
        mod=self.mod
        while idx > 0:
            res_sum += self.BIT[idx]
            res_sum%=mod
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def update(self,idx,x):
        mod=self.mod
        while idx <= self.num:
            self.BIT[idx] += x
            self.BIT[idx]%=mod
            idx += idx&(-idx)
        return

import sys,bisect

input=sys.stdin.readline

mod=10*9+7

N=int(input())
taka=[tuple(map(int,input().split())) for i in range(N)]
taka.sort()

V=[0]+[taka[i][1] for i in range(N)]+[10**15]
cummin=[V[i] for i in range(N+2)]
for i in range(N,-1,-1):
    cummin[i]=min(cummin[i],cummin[i+1])
cummax=[V[i] for i in range(N+2)]
for i in range(1,N+2):
    cummax[i]=max(cummax[i],cummax[i-1])

const=[]
for i in range(1,N+1):
    R=bisect.bisect_right(cummin,V[i])-1
    L=bisect.bisect_left(cummax,V[i])
    const.append((L,R))


Lconst=[(i,10**15) for i in range(N+1)]
for L,R in const:
    pL,pR=Lconst[L]
    Lconst[L]=(L,min(R,pR))


Rconst=[(-1,i) for i in range(N+1)]
for i in range(1,N+1):
    L,R=Lconst[i]
    if R!=10**15:
        pL,pR=Rconst[R]
        Rconst[R]=(max(pL,L),R)


const=[]
for i in range(1,N+1):
    L,R=Rconst[i]
    if L!=-1:
        while const and const[-1][1]>=R:
            const.pop()
        const.append((L,R))

M=len(const)
const=[(-10**15,-10**15)]+const
Rconst=[const[i][1] for i in range(M+1)]
B=BIT(M,mod)
dp=[1]*(M+1)
for i in range(1,M+1):
    L,R=const[i]
    id=bisect.bisect_left(Rconst,L)
    res=(B.query(i-1)-B.query(id-1))%mod
    R=Rconst[id]
    res+=dp[id-1]*(pow(2,R-L+1,mod)-1)%mod
    res%=mod
    dp[i]=res
    if i!=M:
        nR=Rconst[i+1]
        add=dp[i]*(pow(2,nR-R,mod)-1)%mod
        add%=mod
        B.update(i,add)

cnt=0
data=[0]*(N+2)
for i in range(1,M+1):
    L,R=const[i]
    data[L]+=1
    data[R+1]+=-1
for i in range(1,N+2):
    data[i]+=data[i-1]
for i in range(1,N+1):
    if data[i]==0:
        cnt+=1

ans=pow(2,cnt,mod)*dp[M]
ans%=mod
print(ans)

Submission status: Wrong Answer

Solution code:
class BIT():
    def __init__(self,n,mod):
        self.BIT=[0]*(n+1)
        self.num=n
        self.mod=mod

    def query(self,idx):
        res_sum = 0
        mod=self.mod
        while idx > 0:
            res_sum += self.BIT[idx]
            res_sum%=mod
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def update(self,idx,x):
        mod=self.mod
        while idx <= self.num:
            self.BIT[idx] += x
            self.BIT[idx]%=mod
            idx += idx&(-idx)
        return

import sys,bisect

input=sys.stdin.readline

mod=10*9+7

N=int(input())
taka=[tuple(map(int,input().split())) for i in range(N)]
taka.sort()

V=[0]+[taka[i][1] for i in range(N)]+[10**15]
cummin=[V[i] for i in range(N+2)]
for i in range(N,-1,-1):
    cummin[i]=min(cummin[i],cummin[i+1])
cummax=[V[i] for i in range(N+2)]
for i in range(1,N+2):
    cummax[i]=max(cummax[i],cummax[i-1])

const=[]
for i in range(1,N+1):
    R=bisect.bisect_right(cummin,V[i])-1
    L=bisect.bisect_left(cummax,V[i])
    const.append((L,R))


Lconst=[(i,10**15) for i in range(N+1)]
for L,R in const:
    pL,pR=Lconst[L]
    Lconst[L]=(L,min(R,pR))


Rconst=[(-1,i) for i in range(N+1)]
for i in range(1,N+1):
    L,R=Lconst[i]
    if R!=10**15:
        pL,pR=Rconst[R]
        Rconst[R]=(max(pL,L),R)


const=[]
for i in range(1,N+1):
    L,R=Rconst[i]
    if L!=-1:
        const.append((L,R))

M=len(const)
const=[(-10**15,-10**15)]+const
Rconst=[const[i][1] for i in range(M+1)]
B=BIT(M,mod)
dp=[1]*(M+1)
for i in range(1,M+1):
    L,R=const[i]
    id=bisect.bisect_left(Rconst,L)
    res=(B.query(i-1)-B.query(id-1))%mod
    R=Rconst[id]
    res+=dp[id-1]*(pow(2,R-L+1,mod)-1)%mod
    res%=mod
    dp[i]=res
    if i!=M:
        nR=Rconst[i+1]
        add=dp[i]*(pow(2,nR-R,mod)-1)%mod
        add%=mod
        B.update(i,add)

cnt=0
data=[0]*(N+2)
for i in range(1,M+1):
    L,R=const[i]
    data[L]+=1
    data[R+1]+=-1
for i in range(1,N+2):
    data[i]+=data[i-1]
for i in range(1,N+1):
    if data[i]==0:
        cnt+=1

ans=pow(2,cnt,mod)*dp[M]
ans%=mod
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
import fileinput

MODULO = 1000000007
n = 0

# HANDLE INPUT
def handle_input():
    iterator = fileinput.input()
    global n
    n = int(next(iterator))
    takahashis = [None] * n
    for i in xrange(n):
        x, v = next(iterator).split()
        takahashis[i] = (int(x), int(v))
    return takahashis

def build_blocks(takahashis):
    result = [-1] * (n + 1)
    max_velocities = [-MODULO] * (n + 1)
    min_velocities = [MODULO] * (n + 1)
    for i in xrange(n):
        max_velocities[i] = max(max_velocities[i - 1], takahashis[i][1])
    for i in xrange(n-1, -1, -1):
        min_velocities[i] = min(min_velocities[i + 1], takahashis[i][1])
    for i in xrange(n):
        current_velocity = takahashis[i][1]
        block_start = bisect_left(max_velocities, current_velocity)
        block_end = bisect_right(min_velocities, current_velocity) - 1
        result[block_end] = max(result[block_end], block_start)
    return result


def compute_possibilities(blocks):
    possibilities = [1] * (n + 2)
    zeros_end_cursor = -2
    for current_position in xrange(n):
        result = 2 * possibilities[current_position - 1]
        # Remove possibiltiies for (00..)1{.....} sequences.
        while zeros_end_cursor < blocks[current_position] - 1:
            result -= possibilities[zeros_end_cursor]
            zeros_end_cursor += 1
        possibilities[current_position] = result % MODULO
    return possibilities[n - 1]


def main():
    takahashis = handle_input()
    takahashis.sort()
    blocks = build_blocks(takahashis)
    return compute_possibilities(blocks)


if __name__ == '__main__':
    print main()