Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# ---------標準入力時--------------
h,w=map(int,readline().split())
ch, cw=map(int,readline().split())
dh, dw=map(int,readline().split())
m=list(map(lambda x: list(x.decode()), readlines()))
# ---------標準入力時--------------

ch-=1; cw-=1; dh-=1; dw-=1

ad = [(-1,0), (0,-1), (1,0), (0,1)]
warp = [(-2, -2),(-2, -1),(-2, 0),(-2, 1),(-2, 2),
 (-1, -2),(-1, -1),(-1, 1),(-1, 2),
 (0, -2),(0, 2),
 (1, -2),(1, -1),(1, 1),(1, 2),
 (2, -2),(2, -1),(2, 0),(2, 1),(2, 2)]

def bfs3():
    '''
    queue2つ
    '''
    que1=[]
    que2=[] # queueというよりはメモリ
    m[ch][cw]=str(0)
    que1.append((ch,cw))

    while que1!=[]:
        l1=len(que1)
        r1=0 # que1における使用済みindex
        # que1の要素(座標)から歩いていけるマス
        while r1<l1:
            i, j=que1[r1]
            r1+=1
            # 隣接したマスへの移動
            for si, sj in ad:
                if 0<=i+si<h and 0<=j+sj<w and m[i+si][j+sj]=='.': 
                    m[i+si][j+sj]=m[i][j]
                    que1.append((i+si, j+sj))
                    l1+=1

        # 歩いていけないマス
        for i,j in que1:
            for si, sj in warp:
                if 0<=i+si<h and 0<=j+sj<w and m[i+si][j+sj]=='.':
                    m[i+si][j+sj]=str(int(m[i][j])+1)
                    que2.append((i+si, j+sj))

        que1=que2
        que2=[]

bfs3()

if m[dh][dw] == '.':
    print(-1)
else:
    print(m[dh][dw])

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# ---------標準入力時--------------
h,w=map(int,readline().split())
ch, cw=map(int,readline().split())
dh, dw=map(int,readline().split())
m=list(map(lambda x: list(x.decode()), readlines()))
# ---------標準入力時--------------

ch-=1; cw-=1; dh-=1; dw-=1

ad = [(-1,0), (0,-1), (1,0), (0,1)]
warp = [(-2, -2),(-2, -1),(-2, 0),(-2, 1),(-2, 2),
 (-1, -2),(-1, -1),(-1, 1),(-1, 2),
 (0, -2),(0, 2),
 (1, -2),(1, -1),(1, 1),(1, 2),
 (2, -2),(2, -1),(2, 0),(2, 1),(2, 2)]

for i in range(h):
    m[i] = ['#']*2 + m[i] + ['#']*2
    
m = [['#']*(w+4)]*2 + m + [['#']*(w+4)]*2
ch+=2; cw+=2; dh+=2; dw+=2

def bfs4():
    '''
    bfs3とほぼ同じ. 迷路の上下左右に2列ずつ壁追加
    '''
    que1=[]
    que2=[] # queueというよりはメモリ
    m[ch][cw]=str(0)
    que1.append((ch,cw))

    while que1!=[]:
        l1=len(que1)
        r1=0 # que1における使用済みindex

        # que1の要素(座標)から歩いていけるマス
        while r1<l1:
            i, j=que1[r1]
            r1+=1
            # 隣接したマスへの移動
            for si, sj in ad:
                if m[i+si][j+sj]=='.': 
                    m[i+si][j+sj]=m[i][j]
                    que1.append((i+si, j+sj))
                    l1+=1

        # 歩いていけないマス
        for i,j in que1:
            for si, sj in warp:
                if m[i+si][j+sj]=='.':
                    m[i+si][j+sj]=str(int(m[i][j])+1)
                    que2.append((i+si, j+sj))

        que1=que2
        que2=[]
###---------------------------------------

bfs4()


if m[dh][dw] == '.':
    print(-1)
else:
    print(m[dh][dw])
### BUGGY CODE ###



n=input()
cnt=0
for i in range(len(n)-4):
    for j in range(i+5,len(n)+1):
        if int(n[i:j])%2019==0:
            cnt+=1
            break

print(cnt)



### FIXED CODE ###

s=input()



"""
◆エッセンス1：割り切れるとは、二つに分けた数字のmodが一緒
例)
1817181712114の
18171が2019で割り切れるかどうかを判断する。

18171は(181712114-2114)/10000となるので、
181712114mod2019＝2114mod2019の時、2019で割り切れる。

1817181712114mod2019
 817181712114mod2019
  17181712114mod2019
   7181712114mod2019
    181712114mod2019
     81712114mod2019
      1712114mod2019
       712114mod2019
    　　・・・・
とmodを調べていき、値が同じペアは割り切れる。
"""

"""
◆エッセンス2：大きい数字は都度modを取る

これだけでもループは1回になるんだけど、
|S|が長すぎてTLEとなってしまう（|S|は10**5）
1234567 mod 2019
=(1*10**7)mod2019 + (234567mod2019)
=(1*10mod2019 * 10**6mod2019)+ (234567mod2019)

10**nを毎回modを取ることで、計算する数字の長さを短くする。

"""



#modの値を保持する配列
cnt=[0]*2019
#mod2019 =0 は、それ一つで割り切れるので。引き算をする必要が無い。
cnt[0]=1

#10の倍数を保持する
fac=1
ss=0
for i in range(len(s)):
    #後ろの数字から順番にとってくる
    ss += int(s[len(s)-i-1])*fac
    ss%=2019
    fac=fac*10
    fac%=2019
    cnt[ss]+=1
    

result=0
for c in cnt:
    result+=c*(c-1)//2

print(result)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
def lcs_sol(x, y):
    n = len(x)
    m = len(y)
    dp = [0 for j in range(m + 1)]

    for i in range(1, n + 1):
        dp_prev = dp[:]
        for j in range(1, m + 1):
            if x[i - 1] == y[j - 1]:
                dp[j] = dp_prev[j - 1] + 1
            elif dp_prev[j] < dp[j - 1]:
                dp[j] = dp[j - 1]

    return dp[m]


# if __name__ == '__main__':
import sys
q = int(sys.stdin.readline().strip())
for i in range(q):
    x = sys.stdin.readline().strip()
    y = sys.stdin.readline().strip()
    print(lcs_sol(x, y))



### FIXED CODE ###

def m():
 e=input
 a=''
 for _ in[0]*int(e()):
  X,z=e(),[]
  for y in e():
   s=i=0
   for k in z:
    t=X.find(y,s)+1
    if t<1:break
    if t<k:z[i]=t
    s=k;i+=1
   else:
    t=X.find(y,s)+1
    if t:z+=[t]
  a+=f'\n{len(z)}'
 print(a[1:])
if'__main__'==__name__:m()
### BUGGY CODE ###

from collections import deque

INF = float("inf")

H, W, K = map(int, input().split())
A = [list(input()) for _ in range(H)]

Si, Sj = (0, 0)
for i, a in enumerate(A):
    if "S" in a:
        Si, Sj = (i, a.index("S"))
        break

dist = [[INF] * W for _ in range(H)]
dist[Si][Sj] = 0


ans = INF

Q = deque([(Si, Sj)])
while Q:
    i, j = Q.popleft()

    ans = min(
        ans,
        1 + (i + K - 1) // K,
        1 + (j + K - 1) // K,
        1 + (H - 1 - i + K - 1) // K,
        1 + (W - 1 - j + K - 1) // K
    )

    if dist[i][j] == K:
        continue

    distance = dist[i][j] + 1

    for di, dj in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        ni, nj = i + di, j + dj

        if not (0 <= ni < H and 0 <= nj < W) or A[ni][nj] == "#":
            continue

        if dist[ni][nj] > distance:
            dist[ni][nj] = distance
            Q.append((ni, nj))

print(ans)


### FIXED CODE ###

from collections import deque

INF = float("inf")

H, W, K = map(int, input().split())
A = [list(input()) for _ in range(H)]

Si, Sj = (0, 0)
for i, a in enumerate(A):
    if "S" in a:
        Si, Sj = (i, a.index("S"))
        break

dist = [[INF] * W for _ in range(H)]
dist[Si][Sj] = 0


ans = INF

Q = deque([(Si, Sj)])
while Q:
    i, j = Q.popleft()

    ans = min(
        ans,
        1 + (i + K - 1) // K,
        1 + (j + K - 1) // K,
        1 + (H - 1 - i + K - 1) // K,
        1 + (W - 1 - j + K - 1) // K
    )

    if dist[i][j] == K:
        continue

    distance = dist[i][j] + 1

    for di, dj in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        ni, nj = i + di, j + dj

        if not (0 <= ni < H and 0 <= nj < W and A[ni][nj] == "."):
            continue

        A[ni][nj] = "#"

        if dist[ni][nj] > distance:
            dist[ni][nj] = distance
            Q.append((ni, nj))

print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(M)]

# どのグループか
z = [-1] * N
# グループに含まれる数
gcount = [0] * min(N // 2, M)
k = 0


def func1(x, y):
    global z, gcount, k
    px = z[x]
    py = z[y]
    if px > -1 and py > -1:
        if px == py:
            return 0
        else:
            r = gcount[px] * gcount[py]
            for i in range(N):
                if z[i] == py:
                    z[i] = px
            gcount[px] += gcount[py]
            return r
    elif px > -1:
        r = gcount[px]
        z[y] = px
        gcount[px] += 1
        return r
    elif py > -1:
        r = gcount[py]
        z[x] = py
        gcount[py] += 1
        return r
    else:
        z[x] = k
        z[y] = k
        gcount[k] = 2
        k += 1
        return 1


ans = [0] * (M - 1)
p = 0
for q in range(M - 1, 0, -1):
    p += func1(A[q][0] - 1, A[q][1] -1)
    ans[q - 1] = p

nall = N * (N - 1) // 2
for a in ans:
    print(nall - a)
print(nall)

### FIXED CODE ###

N, M = map(int, input().split())
ab = [tuple(map(lambda x:int(x)-1, input().split())) for _ in range(M)]


class UnionFind:
    def __init__(self,size):
        self.rank = [-1 for _ in range(size)]
        self.number = [1 for _ in range(size)]

    def find(self,x):
        while self.rank[x] >= 0:
            x = self.rank[x]
        return x

    def union(self,x,y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 == s2:
            return
        if self.rank[s1] == self.rank[s2]:
            self.rank[s1] -= 1
            self.rank[s2] = s1
            self.number[s1] += self.number[s2]
        elif self.rank[s1] < self.rank[s2]:
            self.rank[s2] = s1
            self.number[s1] += self.number[s2]
        else:
            self.rank[s1] = s2
            self.number[s2] += self.number[s1]


def main():
    uf = UnionFind(N)
    p = N * (N - 1) // 2
    ans = [p]
    for x, y in reversed(ab):
        px = uf.find(x)
        py = uf.find(y)
        if px != py:
            p -= uf.number[px] * uf.number[py]
            uf.union(px, py)
        ans.append(p)

    for a in reversed(ans[:-1]):
        print(a)


main()
### BUGGY CODE ###

def have_AC(str):
    count=0
    for i in range(len(str)):
        if(str[i:i+2]=="AC"):
            count=count+1
    return count

n,q=input().split() #nは文字の長さ　qは質問数
s=input() #Sは文字列
n=int(n)
q=int(q)
num=[]

for i in range(q):
    a,b=input().split()
    a=int(a) -1
    b=int(b)
    num.append(have_AC(s[a:b]))

for j in range(len(num)):
    print(num[j])


### FIXED CODE ###

def have_AC(str):
    count=[0]
    for i in range(1,len(str)):
        if(str[i]=='C' and str[i-1]=='A'):
            count.append(count[i-1]+1)
            continue
        count.append(count[i-1])
    return count

n,q=input().split() #nは文字の長さ　qは質問数
s=input() #Sは文字列
n=int(n)
q=int(q)
num=[]
d=have_AC(s)

for i in range(q):
    a,b=input().split()
    a=int(a)
    b=int(b)
    num.append(d[b-1]-d[a-1])

for j in range(len(num)):
    print(num[j])
### BUGGY CODE ###

n, m = [int(x) for x in input().split()]
a = [int(input()) for _ in range(m)]
# a = [int(x) for x in input().split()]

memo = [0]*(n + 1)

for i in range(n+1):
  if i in a:
    continue
  else:
    if i == 0 or i == 1:
      memo[i] = 1
    else:
      memo[i] = memo[i-1] + memo[i-2]

print(memo[n]%((10**9)+7))


### FIXED CODE ###

n, m = [int(x) for x in input().split()]
a = set([int(input()) for _ in range(m)])
# a = [int(x) for x in input().split()]
 
memo = [0]*(n + 1)
 
for i in range(n+1):
  if i in a:
    continue
  else:
    if i == 0 or i == 1:
      memo[i] = 1
    else:
      memo[i] = (memo[i-1] + memo[i-2])%((10**9)+7)
 
print(memo[n])
### BUGGY CODE ###

import itertools
N = int(input())
S = list(input())
num = 10**9+7
count = 0
for i in range(N):
  for j in list(itertools.combinations(range(N),i)):
    tmp = S[:]
    j = sorted(j,reverse=True)
    for k in j:
      tmp.pop(k)
    if len(tmp) == len(set(tmp)):
      count+=1
print(count%num)



### FIXED CODE ###

N = int(input())
S = list(input())
num = 10**9+7
ans = 1
s = set(S)
for i in s:
  ans *= S.count(i)+1
print(ans%num-1)
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
s=''
for i in range(1,n+1):
    s+=str(l.index(i)+1)+' '
print(s)

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
l2=[0]*(n+1)
for i,j in enumerate(l,1):
    l2[j]=i 
print(' '.join(map(str,l2[1:])))
### BUGGY CODE ###

n = int(input())
a = input().split()
for i in range(1,n+1):
    print(a.index(str(i))+1, end=" ")


### FIXED CODE ###

n = int(input())
lia = [int(s) for s in input().split()]
lib = [0]*n
for i in range(n):
    lib[lia[i] - 1] += i + 1
lic = [str(s) for s in lib]
print(" ".join(lic))
### BUGGY CODE ###

x=float(input())
a=float(100)
y=0
while a<x:
    a*=1.01
    a=a%1
    y+=1
print(y)

### FIXED CODE ###

x=float(input())
a=float(100)
y=0
import math
while a<x:
    a=a*1.01
    a=math.floor(a)
    y+=1
print(y)
### BUGGY CODE ###

s = input()
q = int(input())
tmp = s
flag = 0
for _ in range(q):
    _s = input()
    if _s == "1":
        flag += 1
    else:
        f = _s[2]
        c = _s[4]
        r = flag % 2
        if f == "1" and r == 0:
            tmp = c + tmp
        elif f == "1" and r == 1:
            tmp = tmp + c
        elif f == "2" and r == 0:
            tmp = tmp + c
        elif f == "2" and r == 1:
            tmp = c + tmp
if flag % 2 == 0:
    print(tmp)
else:
    print(tmp[::-1])

### FIXED CODE ###

from collections import deque
s = input()
q = int(input())
tmp = deque()
for i in range(len(s)):
    tmp.append(s[i])
flag = 0
for _ in range(q):
    _s = input()
    if _s == "1":
        flag += 1
    else:
        t, f, c = _s.split(" ")
        r = flag % 2
        if f == "1" and r == 0:
            #tmp = c + tmp
            tmp.appendleft(c)
        elif f == "1" and r == 1:
            #tmp = tmp + c
            tmp.append(c)
        elif f == "2" and r == 0:
            #tmp = tmp + c
            tmp.append(c)
        elif f == "2" and r == 1:
            #tmp = c + tmp
            tmp.appendleft(c)
if flag % 2 == 0:
    for i in range(len(tmp)):
        print(tmp.popleft(), end="")
else:
    for i in range(len(tmp)):
        print(tmp.pop(), end="")
### BUGGY CODE ###

import math
n=int(input())
s = [''.join(sorted(input())) for i in range(n)]
a=set(s)
c=0

for i in a:
    b=s.count(i)
    if b>1:
        c+=(b*(b-1))//2
print(c)

### FIXED CODE ###

n=int(input())
s = [''.join(sorted(input())) for i in range(n)]
s.sort()
s.append("a")
b=1
c=0
for i in range(n):
    if s[i]!=s[i+1]:
        c+=(b*(b-1))//2
        b=1
    else:
        b+=1
print(c)
### BUGGY CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10**6)
def input(): return sys.stdin.readline().strip()

def main():
    N, u, v = map(int, input().split())
    u -= 1
    v -= 1
    repn = [[] for _ in range(N)]
    for i in range(N - 1):
        a, b = map(int, input().split())
        repn[a - 1].append((b - 1, i))
        repn[b - 1].append((a - 1, i)) # (to, id)

    """
    まずu, vを結ぶ単純パス上にあるnodeを列挙する。
    これはvを根とする根付き木に対するdfs（再帰）により求まる（参考：ABC152F）
    """

    path = []
    def connected(v, tv, p=-1):
        if v == tv:
            return True
        for w, _ in repn[v]:
            if w == p:
                continue
            elif connected(w, tv, v):
                path.append(w)
                return True
        return False
    connected(v, u)
    path.append(v)
    #print("path={}".format(path))

    """
    次にu, vを結ぶ単純パスP上の各頂点wに対して、wからPに沿わない向きにどれだけ深く潜れるかを求める。
    ただしu-v間のuより半分だけ求めれば十分。全く潜れない場合を０とする。
    """

    def dfs(v, P): # Pに含まれない頂点方向にdfsして深さを求める
        d = -1
        for w, _ in repn[v]:
            if w in P:
                continue
            else:
                d = max(d, dfs(w, [v]))
        return d + 1
    
    depth = []
    dist = len(path)
    for i, w in enumerate(path):
        if i < dist // 2:
            depth.append(dfs(w, path))
        else:
            break
    #print("depth={}".format(depth))

    """
    これで準備は完了。あとはu-v間の距離から高橋君が青木君から逃げるのにpath上の
    どの頂点から潜るのかを求めればよい。
    """

    ans = 0
    for i in range(dist // 2):
        val = (dist - i - 1) + depth[i] - 1
        ans = max(ans, val)
    print(ans)
   


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10**5)
def input(): return sys.stdin.readline().strip()

"""
Pypyは再帰が遅いらしいのでPythonで通してみる
"""

def main():
    N, u, v = map(int, input().split())
    u -= 1
    v -= 1
    repn = [[] for _ in range(N)]
    for i in range(N - 1):
        a, b = map(int, input().split())
        repn[a - 1].append((b - 1, i))
        repn[b - 1].append((a - 1, i)) # (to, id)

    """
    まずu, vを結ぶ単純パス上にあるnodeを列挙する。
    これはvを根とする根付き木に対するdfs（再帰）により求まる（参考：ABC152F）
    """

    path = []
    def connected(v, tv, p=-1):
        if v == tv:
            return True
        for w, _ in repn[v]:
            if w == p:
                continue
            elif connected(w, tv, v):
                path.append(w)
                return True
        return False
    connected(v, u)
    path.append(v)
    #print("path={}".format(path))

    """
    次にu, vを結ぶ単純パスP上の各頂点wに対して、wからPに沿わない向きにどれだけ深く潜れるかを求める。
    しかし最終的には「頂点vから（高橋君が逃げ込める中で）最も遠い頂点」を求めればよいので、
    uvの中点からdfsすれば十分。
    """

    def dfs(v, p): # Pと異なる頂点方向にdfsして深さを求める
        d = -1
        for w, _ in repn[v]:
            if w == p:
                continue
            else:
                d = max(d, dfs(w, v))
        return d + 1
    
    dist = len(path)
    mid = path[dist // 2 - 1]
    par = path[dist // 2]
    ans = dfs(mid, par)
    print(ans + (dist - 1) // 2)
   


if __name__ == "__main__":
    main()
### BUGGY CODE ###

import numpy

N,K,Q = map(int, input().split())

point = numpy.full(N, K)
lose_point = numpy.ones(N)
for _ in range(Q):
    winnner = int(input())
    point -= lose_point
    point[winnner-1] += 1

for p in point:
    if(p>0):
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

N,K,Q = map(int, input().split())

point = [0] * N
for _ in range(Q):
    winnner = int(input())
    point[winnner-1] += 1

for p in point:
    if(p>Q-K):
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

n = int(input())
l = list(map(int,input().split()))

ans = 0

for i in range(n-1):
  if l[i+1]<=max(l[0:i+1]):
    ans+= max(l[0:i+1])-l[i+1]
    
print(ans)

### FIXED CODE ###

n = int(input())
l = list(map(int,input().split()))

ans = 0

for i in range(n-1):
  if l[i+1]<l[i]:
    ans+= l[i]-l[i+1]
    l[i+1]=l[i]
    
print(ans)
### BUGGY CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
d=[float('inf')]*n
d[0]=0
for i in range(n-1):
    for j in range(1,min(k+1,n-i)):
        d[i+j]=min(d[i+j],d[i]+abs(h[i+j]-h[i]))
print(d[-1])

### FIXED CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
d=[float('inf')]*n
d[0]=0
for i in range(n-1):
    for j in range(1,min(k+1,n-i)):
        d[i+j]=min(d[i+j],d[i]+abs(h[i+j]-h[i]))
print(d[-1])
### BUGGY CODE ###

n=int(input())
A=list(map(int,input().split(" ")))
ans=1
POW=pow(10,18)
check=False
for i in range(n):
  ans*=A[i]
if ans>POW:
  print(-1)
else:
  print(ans)

### FIXED CODE ###

n=int(input())
A=list(map(int,input().split(" ")))
ans=1
POW=pow(10,18)
check=False
answer=1
for i in range(n):
  ans*=A[i]
  if ans>POW:
    ans=0
    check=True
    answer=-1
  if A[i]==0:
    answer=0
if answer<1:
  print(answer)
else:
  print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

MOD = 998244353

N = int(input())
XY = [tuple(int(x) for x in input().split()) for _ in range(N)]
XY.sort() # X ascending
X,Y = zip(*XY)
Y_rank = {x:i for i,x in enumerate(sorted(Y),1)}

def BIT_update(tree,x):
    while x <= N:
        tree[x] += 1
        x += x & (-x)

def BIT_sum(tree,x):
    ret = 0
    while x:
        ret += tree[x]
        x -= x & (-x)
    return ret

pow2 = [1]
for _ in range(N):
    pow2.append(pow2[-1] * 2 % MOD)

answer = 0
tree = [0] * (N+1)
for L,(x,y) in enumerate(XY):
    y = Y_rank[y]
    R = N - 1 - L
    D = y - 1
    U = N - 1 - D
    LD = BIT_sum(tree,y)
    BIT_update(tree,y)
    LU = L - LD
    RD = D - LD
    RU = R - RD
    # bounding box が自分自身を含むような集合を数える
    # 全体から引く
    cnt = pow2[N]
    cnt -= pow2[L]
    cnt -= pow2[R]
    cnt -= pow2[D]
    cnt -= pow2[U]
    cnt += pow2[LD]
    cnt += pow2[LU]
    cnt += pow2[RD]
    cnt += pow2[RU]
    cnt -= 1
    answer += cnt

answer %= MOD

print(answer)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

MOD = 998244353

N = int(input())
XY = [[int(x) for x in input().split()] for _ in range(N)]
XY.sort() # X ascending
X,Y = zip(*XY)
Y_rank = {x:i for i,x in enumerate(sorted(Y),1)}

def BIT_update(tree,x):
    while x <= N:
        tree[x] += 1
        x += x & (-x)

def BIT_sum(tree,x):
    ret = 0
    while x:
        ret += tree[x]
        x -= x & (-x)
    return ret

pow2 = [1]
for _ in range(N):
    pow2.append(pow2[-1] * 2 % MOD)

answer = 0
tree = [0] * (N+1)
for L,(x,y) in enumerate(XY):
    y = Y_rank[y]
    R = N - 1 - L
    D = y - 1
    U = N - 1 - D
    LD = BIT_sum(tree,y)
    BIT_update(tree,y)
    LU = L - LD
    RD = D - LD
    RU = R - RD
    # bounding box が自分自身を含むような集合を数える
    # 全体から引く
    cnt = pow2[N]
    cnt -= pow2[L]
    cnt -= pow2[R]
    cnt -= pow2[D]
    cnt -= pow2[U]
    cnt += pow2[LD]
    cnt += pow2[LU]
    cnt += pow2[RD]
    cnt += pow2[RU]
    cnt -= 1
    answer += cnt

answer %= MOD

print(answer)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2 *(10**5) + 1)
def main():
    N, Q = map(int, input().split())
    d = {}
    for _ in range(N-1):
        a, b = map(int, input().split())
        if a in d:
            d[a].append(b)
        else:
            d[a] = [b]
        if b in d:
            d[b].append(a)
        else:
            d[b] = [a]
    dc = {}
    for _ in range(Q):
        p, x = map(int, input().split())
        if p in dc:
            dc[p] += x
        else:
            dc[p] = x
    v = set()
    l = [0] * N
    def dfs(n, p):
        v.add(n)
        if n in dc:
            p += dc[n]
        for i in d[n]:
            if i not in v:
                dfs(i, p)
        l[n-1] = p
    dfs(1, 0)
    return ' '.join(str(i) for i in l)

print(main())


### FIXED CODE ###

def main():
    N, Q = map(int, input().split())
    d = {}
    for _ in range(N-1):
        a, b = map(int, input().split())
        if a in d:
            d[a].append(b)
        else:
            d[a] = [b]
        if b in d:
            d[b].append(a)
        else:
            d[b] = [a]
    dc = {}
    for _ in range(Q):
        p, x = map(int, input().split())
        if p in dc:
            dc[p] += x
        else:
            dc[p] = x
    v = set()
    vr = set(range(1,N+1))
    l = [0] * N
    n = [(1,0)]
    c = []
    while v != vr:
        for i, j in n:
            v.add(i)
            if i in dc:
                j += dc[i]
            l[i-1] = j
            for k in d[i]:
                if k not in v:
                    c.append((k, j))
        n = c
        c = []
    return ' '.join(str(i) for i in l)

print(main())
### BUGGY CODE ###

n,m=(int(x) for x in input().split())
l = [int(i) for i in input().split()]

l.sort(reverse=True)
for i in range(m):
    l[0]=l[0]//2
    l.sort(reverse=True)
total=sum(l)

print(total)
 

### FIXED CODE ###

import heapq

n, m = map(int, input().split())
a = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(a)  # aを優先度付きキューに

for _ in range(m):
    tmp_min = heapq.heappop(a)
    heapq.heappush(a, (-1)*(-tmp_min//2))  # 計算誤差の関係で-1を2回かけてます
print(-sum(a))
### BUGGY CODE ###

import sys
input=sys.stdin.readline
z=list(map(int,input().split()))
a,b,c=[],[],z[2]-z[1]
for i in range(z[2]):
    a.append(int(input()))
for i in range(z[0]):
    if c-a.count(i+1)>=0:
        print('No')
    else:
        print('Yes')

### FIXED CODE ###

n,k,q=map(int,input().split())
a,b=[int(input()) for _ in range(q)],[0]*n
for i in a:
    b[i-1]+=1
for i in b:
    print('Yes' if i+k-q>0 else 'No')
### BUGGY CODE ###

import sys

sys.setrecursionlimit(1000000)

N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
a.append(N+1)
sum_move = 1
fact = [-1] * (N+1)
fact[0] = 1


def factorial(num, fact):
    if fact[num] > 0:
        return fact[num]
    else:
        fact[num] = factorial(num-1, fact) * num
        return fact[num]


step_begin = 0
for i in range(M+1):
    tmp_sum = 0
    step_end = a[i] - 1
    step_num = step_end - step_begin
    for j in range(step_num//2 + 1):
        tmp_sum += factorial(step_num - j, fact) \
            // factorial(j, fact) // factorial(step_num - 2 * j, fact)
    if tmp_sum != 0:
        sum_move *= tmp_sum
    else:
        sum_move = 0
        break
    step_begin = step_end + 2

print(sum_move % 1000000007)

### FIXED CODE ###

N, M = map(int, input().split())
oks = [True] * (N+1)
a = [int(input()) for _ in range(M)]
for i in a:
    oks[i] = False

dp = [0] * (N+1)
dp[0] = 1
for i in range(N+1):
    for j in range(i+1, min(i+2, N)+1):
        if oks[j]:
            dp[j] += dp[i]
            dp[j] %= int(1e9+7)


print(dp[N])