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

n=int(input())
a=list(map(int,input().split()))
b=sorted(list(map(int,input().split())))
c=sorted(list(map(int,input().split())))

def binarySearch(i,lst):
	#(lb,ub]で持って、条件式を実現する最小のdを求める
	lb=-1
	ub=n-1
	if lst[ub]<=i:
		return n
	while ub-lb>1:
		mid=(lb+ub)//2
		if lst[mid]>i:
			ub=mid
		else:
			lb=mid
	return ub

ans=0
for i in range(n):
	b_minindex=binarySearch(a[i],b)
	for j in range(b_minindex,n):
		if b_minindex==n:
			break
		c_minindex=binarySearch(b[j],c)
		ans+=n-c_minindex
print(ans)

### FIXED CODE ###

n=int(input())
a=sorted(list(map(int,input().split())))
b=sorted(list(map(int,input().split())))
c=sorted(list(map(int,input().split())))

def binarySearchA(i,lst):
	#[lb,ub)で持って、条件式を実現する最大のindexを求める
	#indexが小さいほど実現しやすいとき。
	lb=0
	ub=n
	if lst[0]>=i:
		return -1
	while ub-lb>1:
		mid=(lb+ub)//2
		if lst[mid]<i:
			lb=mid
		else:
			ub=mid
	return lb

def binarySearchB(i,lst):
	#(lb,ub]で持って、条件式を実現する最小のindexを求める
	lb=-1
	ub=n-1
	if lst[ub]<=i:
		return n
	while ub-lb>1:
		mid=(lb+ub)//2
		if lst[mid]>i:
			ub=mid
		else:
			lb=mid
	return ub

ans=0
for i in b:
	a_max=binarySearchA(i,a)
	c_min=binarySearchB(i,c)
	ans+=(a_max+1)*(n-c_min)
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
for i in range(N):
    if A.count(A[i]) > 1:
        print('NO')
        exit()
print('YES')

### FIXED CODE ###

N = int(input())
A = list(input().split())
A.sort()
for i in range(N-1):
    if A[i]==A[i+1]:
        print('NO')
        exit()
print('YES')
### BUGGY CODE ###

#https://atcoder.jp/contests/abc122/tasks/abc122_c
N,Q= map(int,input().split())
moji = str(input())
for i in range(Q):
    start,stop = map(int,input().split())
    print(moji[start-1:stop].count("AC"))

    


### FIXED CODE ###

N,K = map(int,input().split())
moji = str(input())
ans = [0]
for i in range(N-1):
    if moji[i] == "A" and moji[i+1] == "C":
        ans.append(ans[i]+1)
    else:
        ans.append(ans[i])

        
for i in range(K):
    st,sp = map(int,input().split())
    print(ans[sp-1]-ans[st-1])
### BUGGY CODE ###

def popcount(n):
    a = 0
    while n:
        a += n % 2
        n //= 2
    return a

def fun(n, pc):
    if n == 0:
        return 0
    n %= pc

    ops = 1
    while n:
        bits = popcount(n)
        n = n % bits
        ops += 1
    return ops

n = int(input())
xs = list(map(int, input()))

from functools import reduce
sm = reduce(lambda x,y: x*2+y, xs)
pc = xs.count(1)

for i in range(n):
    xs[i] ^= 1
    df = 1 if xs[i] == 1 else -1
    pc += df

    dn = 1 << (n - (i + 1))
    smi = sm + dn * df

    print(fun(smi, pc))

    xs[i] ^= 1
    pc -= df


### FIXED CODE ###

from numba import njit

@njit('i8(i8)', cache=True)
def popcount(n):
    a = 0
    while n != 0:
        a += n & 1
        n >>= 1
    return a

@njit('i8(i8)', cache=True)
def fun(n):
    ops = 0
    while n:
        pc = popcount(n)
        n %= pc
        ops += 1
    return ops

n = int(input())
xs = list(map(int, input()))

from functools import reduce
sm = reduce(lambda x,y: x*2+y, xs)
pc = xs.count(1)

# pcの差分を出した後の剰余計算を速くするため、事前にmod pc+1, mod pc-1を計算しておく
mp = sm % (pc + 1)
mm = sm % (pc - 1) if pc > 1 else 0

for i in range(n):
    df = 1 if xs[i] == 0 else -1
    pci = pc + df
    if pci == 0:
        print(0)
        continue

    rest = pow(2, n - i - 1, pci)

    if xs[i] == 0:
        smi = (mp + rest) % pci
        print(1 + fun(smi))
    else:
        smi = (mm - rest) % pci
        print(1 + fun(smi))
### BUGGY CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
l = 29
val = 0
from bisect import bisect_left as bl, bisect_right as br
    
for k in range(l):
    # i桁目を求める
    tmp = pow(2, k+1)
    bb = [item%(tmp) for item in b]
    bb.sort()
    ans = 0
    for item in a:
        aa = item%tmp
        if aa<=tmp//2:
            ans += (br(bb, tmp-1-aa) - bl(bb, tmp//2-aa))%2
        else:
            ans += (br(bb, tmp-1-aa) + (n - bl(bb, tmp//2*3-aa)))%2
    if ans%2:
        val += pow(2, k)
print(val)

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
l = 29
val = 0

def lcount(a,b,x):
    """ソート済a,bに対して, a[i]+b[j]<=xなるi,jの個数
    """
    la = len(a)
    lb = len(b)
    j = -1
    ans = 0
    for i in range(la-1, -1, -1):
        while j+1<lb and a[i]+b[j+1]<=x:
            j += 1
        ans += (j+1)
    return ans
for k in range(l):
    # i桁目を求める
    tmp = pow(2, k+1)
    bb = [item%(tmp) for item in b]
    aa = [item%(tmp) for item in a]
    aa.sort()
    bb.sort()
    ans = n**2 - lcount(aa,bb,tmp//2*3-1) + lcount(aa,bb,tmp-1) - lcount(aa,bb,tmp//2-1)
    if ans%2:
        val += pow(2, k)
print(val)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
from sys import exit

N = int(input())
a = [[int(e) - 1 for e in input().split()] for _ in range(N)]

id = [[0] * N for _ in range(N)]
def toId(i, j):
  if i > j:
    i, j = j, i
  return id[i][j]

visited = [False] * (N * (N - 1) // 2)
calculated = [False] * (N * (N - 1) // 2)
dp = [0] * (N * (N - 1) // 2)
to = [[] for _ in range(N * (N - 1) // 2)]

def dfs(v):
  if visited[v]:
    if not calculated[v]:
      return -1
    return dp[v]
  visited[v] = True
  dp[v] = 1
  for u in to[v]:
    res = dfs(u)
    if res == -1:
      return -1
    dp[v] = max(dp[v], res + 1)
  calculated[v] = True
  return dp[v]

v = 0
for i in range(N):
  for j in range(N):
    if i >= j:
      continue
    id[i][j] = v
    v += 1

for i in range(N):
  for j in range(N - 1):
    a[i][j] = toId(i, a[i][j])
  for j in range(N - 2):
    to[a[i][j + 1]].append(a[i][j])

ans = 0
for i in range(N * (N - 1) // 2):
  res = dfs(i)
  if res == -1:
    print('-1')
    exit()
  ans = max(ans, res)
print(ans)


### FIXED CODE ###

from sys import exit, setrecursionlimit
setrecursionlimit(1000000)

def dfs(v, dp, to):
  t = dp[v]
  if t >= 0:
    return t
  dp[v] = 0
  t = 0
  for u in to[v]:
    res = dfs(u, dp, to)
    if res == 0:
      print('-1')
      exit()
    if res > t:
      t = res
  t += 1
  dp[v] = t
  return t

def toId(i, j, id_db):
  if i < j:
    return id_db[i][j]
  else:
    return id_db[j][i]

def main():
  N = int(input())
  a = [[int(e) - 1 for e in input().split()] for _ in range(N)]

  id_db = [[0] * N for _ in range(N)]

  dp = [-1] * (N * (N - 1) // 2)
  to = [[] for _ in range(N * (N - 1) // 2)]

  v = 0
  for i in range(N):
    for j in range(i + 1, N):
      id_db[i][j] = v
      v += 1

  for i in range(N):
    for j in range(N - 1):
      a[i][j] = toId(i, a[i][j], id_db)
    for j in range(N - 2):
      to[a[i][j + 1]].append(a[i][j])

  print(max(dfs(i, dp, to) for i in range(N * (N - 1) // 2)))

main()
### BUGGY CODE ###

n,q = map(int,input().split())
s = list(input())
l = len(s)
for i in range(l-1):
  if s[i] == "A" and s[i+1] == "C":
    s[i]= "a"


lis = [0]*(l+1)
for i in range(l+1):
  lis[i] = s[:i].count("a")


for i in range(q):
  l,r = map(int,input().split())
  print(lis[r-1]-lis[l-1])
  
  



### FIXED CODE ###

n,q = map(int,input().split())
s = list(input())
l = len(s)
for i in range(l-1):
  if s[i] == "A" and s[i+1] == "C":
    s[i]= "a"


lis = [0]*(l+1)
for i in range(1,l+1):
  lis[i] = lis[i-1]+(1 if s[i-1]=="a" else 0)


for i in range(q):
  l,r = map(int,input().split())
  print(lis[r-1]-lis[l-1])
### BUGGY CODE ###

import sys
input=sys.stdin.readline
import heapq
def dijkstra(x,route):
    n=len(route)
    d=[float('inf')]*n
    d[x]=0
    Visited=[False]*n
    hq=[(0,x)]
    while hq:
        u=heapq.heappop(hq)[1]
        Visited[u]=True
        for v,cost in route[u]:
            if (not Visited[v]) and d[v]>d[u]+cost:
                d[v]=d[u]+cost
                heapq.heappush(hq,(d[v],v))
    return d

def dist(V1,V2):
    return max(0,((V2[0]-V1[0])**2+(V2[1]-V1[1])**2)**0.5-(V1[2]+V2[2]))

sx,sy,gx,gy=map(int,input().split())
n=int(input())
V=[(sx,sy,0)]+[tuple(map(int,input().split())) for _ in range(n)]+[(gx,gy,0)]
Edges=[[] for _ in range(n+2)]
for i in range(n+1):
    for j in range(i+1,n+2):
        d=dist(V[i],V[j])
        Edges[i].append((j,d))
        Edges[j].append((i,d))
print(dijkstra(0,Edges)[-1])

### FIXED CODE ###

import sys
input=sys.stdin.readline

def dijkstra(s,n,Cost):
    D=[float('inf')]*n
    Visited=[False]*n
    D[s]=0
    while True:
        v=-1
        for i in range(n):
            if (not Visited[i]) and v==-1:
                v=i
            elif (not Visited[i]) and D[i]<D[v]:
                v=i
        if v==-1:
            break
        Visited[v]=True
        for j in range(n):
            D[j]=min(D[j],D[v]+Cost[v][j])
    return D

def dist(V1,V2):
    return max(0,((V2[0]-V1[0])**2+(V2[1]-V1[1])**2)**0.5-(V1[2]+V2[2]))

sx,sy,gx,gy=map(int,input().split())
n=int(input())
V=[(sx,sy,0)]+[tuple(map(int,input().split())) for _ in range(n)]+[(gx,gy,0)]
Cost=[[float('inf')]*(n+2)for _ in range(n+2)]
for i in range(n+1):
    for j in range(i,n+2):
        d=dist(V[i],V[j])
        Cost[i][j]=d; Cost[j][i]=d
print(dijkstra(0,n+2,Cost)[-1])
### BUGGY CODE ###

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

def main(i):
  a = A[i-1:n-1].count(i)
  print(a)


for i in range(1,n+1):
  main(i)

### FIXED CODE ###

from collections import Counter
n = int(input())
A = list(map(int,input().split()))

mycounter = Counter(A)

for i in range(1,n+1):
  print(mycounter[i])
### BUGGY CODE ###

N,M=map(int,input().split())
from collections import defaultdict,deque
branch=defaultdict(dict)
for i in range(M):
    a,b,c=map(int,input().split())
    branch[a-1][b-1]=c
inf=10**15
dist=[(-inf,set())]*N
dist[0]=(0,{0})
check={0}
while len(check)>0:
    now=check.pop()
    for nex,s in branch[now].items():
        if nex not in dist[now][1]:
            dist[nex]=(dist[now][0]+s,dist[now][1]|{nex})
            check|={nex}
        elif dist[now][0]>=inf:
            continue
        elif dist[now][0]+s>dist[nex][0]:
            dist[nex]=(inf,{nex})
            check|={nex}
if dist[N-1][0]>=inf:
    print('inf')
else:
    print(dist[N-1][0])

### FIXED CODE ###

N,M=map(int,input().split())
big=10**13
data=[-1*float('inf')]*(N+1)
from collections import defaultdict
branch=defaultdict(set)
for i in range(M):
    a,b,c=map(int,input().split())
    branch[a]|={(b,c),}
from collections import deque
check=deque()
check.append((1,0,set()))
data[1]=0
while len(check)>0:
    now=check.popleft()
    for b,c in branch[now[0]]:
        if now[1]+c>data[b]:
            if data[b]>big:continue
            if b in now[2]:
                data[b]=float('inf')
                check.append((now[0],float('inf'),now[2]|{now[0],b}))
                check.append((b,float('inf'),now[2]|{now[0],b}))
            else:
                data[b]=now[1]+c
                check.append((b,now[1]+c,now[2]|{now[0],}))
if data[N]>big:print('inf')
else:print(data[N])
### BUGGY CODE ###

n = int(input())
s = input()
ans = 0
for i in range(1, n-1):
    for j in range(i+1, n):
        for k in range(j+1, n+1):
            if  j-i != k-j:
                if s[i-1] != s[j-1] and s[i-1] != s[k-1] and s[j-1] != s[k-1]:
                    ans += 1
print(ans)


### FIXED CODE ###

n = int(input())
s = input()
r = s.count("R")
g = s.count("G")
b = s.count("B")
ans = r * g * b
for i in range(1, 1+n//2):
    for j in range(1, n-i*2+1):
        if s[j-1] != s[j+i-1] and s[j-1] != s[j+i*2-1] and s[j+i-1] != s[j+i*2-1]:
                ans -= 1
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main(): 
    H, W, D = LI()
    mod_array = [[0 for _ in range(H*W//D+1)] for _ in range(D)]
    for row_number in range(H):
        row = LI()
        for column_number, item in enumerate(row):
            mod_array[item%D][item//D] = (row_number, column_number)

    # print(mod_array)

    Q = II()
    for _ in range(Q):
        L, R = LI()
        ans = 0
        prev_position = mod_array[L%D][L//D]
        for position in mod_array[L%D][L//D+1:R//D+1]:
            ans += abs(prev_position[0] - position[0]) + abs(prev_position[1] - position[1])
            prev_position = position
        print(ans)
        

main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main(): 
    H, W, D = LI()
    mod_array = [[(0,0) for _ in range(H*W//D+1)] for _ in range(D)]
    for row_number in range(H):
        row = LI()
        for column_number, item in enumerate(row):
            mod_array[item%D][item//D] = (row_number, column_number)

    # print(mod_array)

    mod_array_cumsum = [[0 for _ in range(H*W//D+1)] for _ in range(D)]
    for row_number in range(D):
        cumsum = 0
        prev_position = mod_array[row_number][0]
        for column_number in range(1, H*W//D+1):
            position = mod_array[row_number][column_number]
            cumsum += abs(prev_position[0] - position[0]) + abs(prev_position[1] - position[1])
            mod_array_cumsum[row_number][column_number] = cumsum
            prev_position = position

    # print(mod_array_cumsum)

    Q = II()
    for _ in range(Q):
        L, R = LI()
        ans = mod_array_cumsum[L%D][R//D] - mod_array_cumsum[L%D][L//D]
        print(ans)
        

main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    def calc(n, mod):
        f = 1
        for m in range(1, n + 1):
            f *= m
            f %= mod
        fn = f
        inv = pow(f, mod - 2, mod)
        invs = [1] * (n + 1)
        invs[n] = inv
        for m in range(n, 1, -1):
            inv *= m
            inv %= mod
            invs[m - 1] = inv 
        return fn, invs

    mod = 10**9+7 
    n,a,b=map(int,input().split())
    ans=0
    fn,invs=calc(n,mod)
    for i in range(1,n+1):
        if i==a or i==b:
            continue
        else:
            ans+=(fn*invs[i]*invs[n-i])%mod
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    mod = 10**9+7
    n,a,b=map(int,input().split())
    f=1
    fa=0
    for i in range(1,b+1):
        f=(f*(n-i+1)*pow(i,mod-2,mod))%mod
        if i==a:
            fa=f
    ans=(pow(2,n,mod)-fa-f-1)%mod
    print(ans)

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

from collections import Counter
import sys
sys.setrecursionlimit(10 ** 7)
N = int(input())
A = list(map(int, input().split()))
C = Counter(A)
dp = [[[0.0] * (N+1) for _ in range(N+1)] for _ in range(N+1)]

def rec(x, y, z):
    if dp[x][y][z] != 0:
        return dp[x][y][z]
    if x + y + z == 0:
        return 0
    res = N
    if x > 0:
        res += x * rec(x-1, y, z)
    if y > 0:
        res += y * rec(x+1, y-1, z)
    if z > 0:
        res += z * rec(x, y+1, z-1)
    dp[x][y][z] = res / (x + y + z)
    return dp[x][y][z]

print(rec(C[1], C[2], C[3]))

### FIXED CODE ###


N = int(input())
A = list(map(int, input().split()))
C = [0, A.count(1), A.count(2), A.count(3)]
dp = [[[0.0] * (N+1) for _ in range(N+1)] for _ in range(N+1)]

for k in range(C[3]+1):
    for j in range(C[3]+C[2]+1-k):
        for i in range(N+1-j-k):
            if i + j + k == 0:
                continue
            res = N
            if i > 0:
                res += i * dp[i-1][j][k]
            if j > 0:
                res += j * dp[i+1][j-1][k]
            if k > 0:
                res += k * dp[i][j+1][k-1]
            dp[i][j][k] = res / (i + j + k)
 
print(dp[C[1]][C[2]][C[3]])
### BUGGY CODE ###

h, w, m = map(int, input().split())
bord_x, bord_y = [0 for i in range(h)], [0 for i in range(w)]
bord = [[0 for _i in range(w)] for _j in range(h)]
hw = []
for _i in range(m):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    hw.append([s, t])
    bord_x[s] += 1
    bord_y[t] += 1

x_max, y_max = max(bord_x), max(bord_y)
a = [x for x, p in enumerate(bord_x) if x_max==p]
b = [y for y, p in enumerate(bord_y) if y_max==p]

checker = 0
for i, j in hw:
    if (i in a) and (j in b):
        checker += 1 

if checker == len(a)*len(b):
    print(x_max+y_max-1)
else:
    print(x_max+y_max)

### FIXED CODE ###

h, w, m = map(int, input().split())
bord_x, bord_y = [0]*h, [0]*w
 
hw = []
for _i in range(m):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    bord_x[s] += 1
    bord_y[t] += 1
    hw.append([s, t])
 
x_max, y_max = max(bord_x), max(bord_y)
 
cnt = 0
for i, j in hw:
    if bord_x[i] == x_max and bord_y[j] == y_max:
        cnt += 1
 
if cnt == bord_x.count(x_max)*bord_y.count(y_max):
    x_max -= 1
 
print(x_max+y_max)
### BUGGY CODE ###

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

dp = [0] * (W + 1)
for n in range(N):
	w, v = WV[n]
	for sumw in range(W, w - 1, -1):
		dp[sumw] = max(dp[sumw], dp[sumw - w] + v)
	#for x in dp:
	#	print("{:4d}".format(x), end="")
	#print()
print(max(dp))


### FIXED CODE ###

def dp():
  N, W = map(int, input().split())
  WV = (map(int, input().split()) for _ in range(N))

  DP = [0] * (W+1)
  for w, v in WV:
    for j in range(W, w-1, -1):
      dp = DP[j-w] + v 
      if DP[j] < dp:
        DP[j] = dp
  return max(DP)
print(dp())
### BUGGY CODE ###

#!/usr/bin/env python3
# -*- coding:utf-8 -*-


if __name__=='__main__':
  N, K = map(int, input().split())
  sushis = sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x:x[1], reverse=True)

  curr = sushis[:K]
  leave = sushis[K:]
  base = lambda li: sum([l[1] for l in li])
  types_max = len(set([c[0] for c in sushis]))
  types = set()
  dups = []

  for c in curr:
    if c[0] in types:
      dups += [c]
    else:
      types = types.union({c[0]})

  ps = base(curr) + len(types)**2
  di = {}
  di[len(types)] = ps
  n_types = len(types) + 1
  for l in leave:
    if len(types) >= types_max:
      break
    if len(dups) == 0:
      break
    if not l[0] in types:
      dup = dups.pop()
      di[n_types] = ps - dup[1] + l[1] + n_types**2 - (n_types-1)**2
      ps = di[n_types]
      n_types += 1
      types = types.union({l[0]})

  print(sorted(di.items(), key=lambda x:x[1])[-1][1])

### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding:utf-8 -*-

import sys
input = sys.stdin.readline

def main():
  N, K = map(int, input().split())
  sushis = [tuple(map(int, input().split())) for _ in range(N)]
  sushis.sort(key=lambda x:x[1], reverse=True)
  curr = sushis[:K]
  leave = sushis[K:]
  base = lambda li: sum([l[1] for l in li])
  types_max = len(set([c[0] for c in sushis]))
  types = set()
  dups = []

  for c in curr:
    if c[0] in types:
      dups += [c]
    else:
      types.add(c[0])
  types = set(types)

  ps = base(curr) + len(types)**2
  di = {}
  di[len(types)] = ps
  n_types = len(types) + 1
  for l in leave:
    if len(types) >= types_max:
      break
    if len(dups) == 0:
      break
    if not l[0] in types:
      dup = dups.pop()
      di[n_types] = ps - dup[1] + l[1] + n_types**2 - (n_types-1)**2
      ps = di[n_types]
      n_types += 1
      types.add(l[0])

  print(sorted(di.items(), key=lambda x:x[1])[-1][1])


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

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import connected_components


class People:
    def __init__(self):
        self.frends = []
        self.blocks = []


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

data=[1]*(2*m)
row=[]
col=[]
peoples = [People() for i in range(n + 1)]
for i in range(m):
    one, two = [int(j) for j in input().split()]
    row.append(one)
    row.append(two)
    col.append(two)
    col.append(one)
    peoples[one].frends.append(two)
    peoples[two].frends.append(one)

frends = csr_matrix((data, (row, col)), shape=(n+1, n+1))


num, labels = connected_components(frends)
labels=list(labels)

for i in range(k):
    one, two = [int(j) for j in input().split()]
    if labels[one] == labels[two]:
        peoples[one].blocks.append(two)
        peoples[two].blocks.append(one)

renketu_num = [0]
for i in range(1, num + 1):
    renketu_num.append(labels.count(i))


def get_renketu_num(i):
    return renketu_num[labels[i]] - 1


def get_friend_num(i):
    return len(peoples[i].frends)


def get_block_num(i):
    return len(peoples[i].blocks)


for i in range(1, n + 1):
    print(get_renketu_num(i) - get_friend_num(i) - get_block_num(i))


### FIXED CODE ###

import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

import sys
sys.setrecursionlimit(10**9)
n,m,k=[int(i) for i in input().split()]
frends_num=[0 for i in range(n)]
def make_frends(m,n):
    data=[1 for i in range(m)]

    row=[]
    col=[]
    for k in range(m):
        i,j=[int(l) for l in input().split()]
        new_i=min(i,j)-1
        new_j=max(i,j)-1
        row.append(new_i)
        col.append(new_j)
        frends_num[new_i]+=1
        frends_num[new_j]+=1
    frend_sparce_matrix=csr_matrix((data, (row, col)),shape=(n,n))
    return frend_sparce_matrix


frends=make_frends(m,n)
l,labels=connected_components(frends)
labels
labels=list(labels)

class Group:
    def __init__(self,labels):
        self.labels=labels
        self.group_num=[0 for i in range(l)]
        for i in labels:
            self.group_num[i]+=1
    def get_group_num(self,i):
        return self.group_num[self.labels[i]]

group=Group(labels)


def get_frend_num(i):
    return frends_num[i]


def make_block(k,n):
    block_num=[0 for i in range(n)]
    for p in range(k):
        i,j =[int(l)-1 for l in input().split()]
        new_i=min(i,j)
        new_j=max(i,j)
        if labels[new_i]==labels[new_j]:
            block_num[i]+=1
            block_num[j]+=1
    return block_num

block=make_block(k,n)

def get_block_num(i):
    return block[i]

ans=[]
for i in range(n):
    ans.append(str(group.get_group_num(i)-1-get_frend_num(i)-get_block_num(i)))
print(" ".join(ans))
### BUGGY CODE ###

# -*- coding: utf-8 -*-

mod = 1000000007
def choiceCnt(target_cnt, select_cnt):

    ret_1 = 0
    temp_list = []
    for temp in range(select_cnt):
        temp_list.append(target_cnt - temp)

    bunnsi = 1
    for sub in temp_list:
        bunnsi *= sub

    bunbo = 1
    for sub in range(1, select_cnt + 1):
        bunbo *= sub

    return bunnsi // bunbo


n, a, b = map(int, input().split())

hana_kind_cnt = n

result = 0
for hanataba_koho_select_cnt in range(1, hana_kind_cnt + 1):
    if not(hanataba_koho_select_cnt == a or hanataba_koho_select_cnt == b):
        result += choiceCnt(n, hanataba_koho_select_cnt) % mod

print(int(result))


### FIXED CODE ###

# -*- coding: utf-8 -*-
from functools import reduce

MOD = 1000000007

def power_func(a, b, mod):
    if b == 0: return 1
    if b % 2 == 0:
        d = power_func(a, b // 2, mod)
        return d * d % mod
    if b % 2 == 1:
        return (a * power_func(a, b - 1, mod)) % mod

def nCr(n, r, mod):

    min_r = min(r, n-r)

    if min_r == 1: return n


    bunsi = reduce(lambda x, y: (x * y) % mod, range(n, n-r, -1))
    bunbo = reduce(lambda x, y: (x * y) % mod, range(r, 1, -1))

    return bunsi * power_func(bunbo, mod - 2, mod) % mod


n, a, b = [int(i) for i in input().split()]

print(((power_func(2, n, MOD) -1) - nCr(n, a, MOD)- nCr(n, b, MOD)) % MOD)