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

import queue
def main():
    n,m,k=map(int,input().split())
    root={}
    ng={}
    friend={}
    for i in range(n):
        root[i]=[]
        ng[i]=[0]*n
        ng[i][i]=1
        friend[i]=[0]*n
    for i in range(m):
        a,b=map(int,input().split())
        root[a-1].append(b-1)
        root[b-1].append(a-1)
        friend[a-1][b-1]=1
        friend[b-1][a-1]=1
    for i in range(k):
        a,b=map(int,input().split())
        ng[a-1][b-1]=1
        ng[b-1][a-1]=1
    
    Vstd=[]
    checkVst=[0]*n
    num=[0]*n
    ToVst=queue.Queue()
    for i in range(n):
        Vstd=[]
        if checkVst[i]==1:
            continue
        now=i
        Vstd.append(now)
        checkVst[now]=1
        for kouho in root[now]:
            if checkVst[kouho]!=1:
                ToVst.put(kouho)
                checkVst[kouho]=1
        while ToVst.empty()==False:
            now=ToVst.get()
            Vstd.append(now)
            checkVst[now]=1
            for kouho in root[now]:
                if checkVst[kouho]==1:
                    continue
                ToVst.put(kouho)
                checkVst[kouho]=1

        l=len(Vstd)
        for x in Vstd:
            num[x]=l
            for y in Vstd:
                if ng[x][y]==1 or friend[x][y]==1:
                    num[x]-=1
    print(*num)
    #print(" ".join(map(str,num)))
   

if __name__=="__main__":
    main()
    

### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


n,m,k=map(int,input().split())
uf=UnionFind(n)
block={}
for i in range(n):
    block[i]=[i]
for i in range(m):
    a,b=map(int,input().split())
    uf.union(a-1,b-1)
    block[a-1].append(b-1)
    block[b-1].append(a-1)
    
for i in range(k):
    a,b=map(int,input().split())
    block[a-1].append(b-1)
    block[b-1].append(a-1)
ans=[]
#print(block)
for i in range(n):
    res=uf.size(i)
 #   print(res)
    for value in block[i]:
        if uf.same(value,i):
            res-=1
    ans.append(res)
print(*ans)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split(' ')))

Asum=0
for i in range(N):
  for j in range(i):
    Asum+=A[i]*A[j]
    Asum%=10**9+7

print(Asum)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split(' ')))

AjtoN=sum(A)
Asum=0
for i in range(N):
    AjtoN-=A[i]
    Asum+=A[i]*AjtoN
    Asum=Asum%(10**9+7)

print(Asum)
### BUGGY CODE ###

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

N, A, B = map(int, input().split())
H = []
c = 0
for i in range(N):
    H.append(int(input()))

while max(H) > 0:
    index = max(enumerate(H), key=lambda x: x[1])[0]
    H[index] -= A
    for i in range(len(H)):
        if i != index:
            H[i] -= B
    c += 1

print(c)

### FIXED CODE ###

import math

def bs(n, a, b, hp, min=0, max=10**9):
    left = min
    right = max
    def count(num):
        base = b * num
        attackcount = 0
        diff = a-b
        for i in range(n):
            tmp = math.ceil((hp[i] - base) / diff)
            if tmp <= 0:
                pass
            else:
                attackcount += tmp
        if attackcount <= num:
            return True
        else:
            return False
    while left != right:
        mid = (left + right) // 2
        if count(mid):
            right = mid
        else:
            left = mid + 1
    return left

if __name__ == '__main__':
    n, a, b = map(int, input().split())
    hp = [int(input()) for i in range(n)]
    print(bs(n, a, b, hp))
### BUGGY CODE ###

N,K=map(int,input().split())
Points=[[int(i) for i in input().split()] for i in range(N)]
List_x=[Points[i][0] for i in range(N)]
List_x.sort(key=lambda x:x)
List_y=[Points[i][1] for i in range(N)]
List_y.sort(key=lambda x:x)
n=0
S=[]
for x1 in range(N-1):
  for x2 in range(x1+K-1,N):
    for y1 in range(N-1):
      for y2 in range(y1+K-1,N):
        for p in Points:
          if List_x[x1]<=p[0]<=List_x[x2] and List_y[y1]<=p[1]<=List_y[y2]:
            n+=1
        if n>=K:
          x_delta=List_x[x2]-List_x[x1]
          y_delta=List_y[y2]-List_y[y1]
          S.append(x_delta*y_delta)
          n=0
          break
        n=0
print(min(S))          
          

### FIXED CODE ###

N,K=map(int,input().split())
Points=[[int(i) for i in input().split()] for i in range(N)]
List_x=[Points[i][0] for i in range(N)]
List_x.sort(key=lambda x:x)
List_y=[Points[i][1] for i in range(N)]
List_y.sort(key=lambda x:x)
n=0
Y=0
S=[]
for x1 in range(N-1):
  for x2 in range(x1+K-1,N):
    for y1 in range(N-1):
      for y2 in range(max([y1+K-1,Y]),N):
        for p in Points:
          if List_x[x1]<=p[0]<=List_x[x2] and List_y[y1]<=p[1]<=List_y[y2]:
            n+=1
          if n==K:
            x_delta=List_x[x2]-List_x[x1]
            y_delta=List_y[y2]-List_y[y1]
            S.append(x_delta*y_delta)
            break
        if n>=K:
          n=0
          Y=y2
          break  
        n=0
    Y=0    
print(min(S))
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
S=sum(A)
print(min(abs(S-2*sum(A[i:])) for i in range(1,N)))

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
S=sum(A)
T=[0]*N
for i in range(N-1):
    T[i+1]=T[i]+A[i]
print(min(abs(S-2*T[i]) for i in range(1,N)))
### BUGGY CODE ###

a,b,c,k=map(int,input().split())
n1=1
n2=0
if a==b:print(0);exit()
for i in range(k):
    n1,n2=n2*2,n1+n2
    if abs((n1-n2)*(a-b))>10**18:print("Unfair");exit()
print((n1-n2)*(a-b))

### FIXED CODE ###

a,b,c,k=map(int,input().split())
t=-1
if k%2==0:t=1
print(t*(a-b))
### BUGGY CODE ###

K, S = map(int, input().split())

count = 0
for x in range(0, K+1):
    for y in range(0, K+1):
        for z in range(0, K+1):
            if x + y + z == S:
                count += 1

print(count)

### FIXED CODE ###

K, S = map(int, input().split())

count = 0
for X in range(K+1):
    for Y in range(K+1):
        if 0 <= (S-X-Y) <= K:
            count += 1

print(count)
### BUGGY CODE ###

H,N = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(N)]
dp = [[0 if i == 0 else float("inf") for i in range(H+1)] for j in range(N+1)]
for n in range(N):
  for h in range(1,H+1):
    if h < AB[n][0]:
      dp[n+1][h] = min([dp[n][h], AB[n][1]])
    else:
      dp[n+1][h] = min([dp[n][h], dp[n+1][h-AB[n][0]]+AB[n][1]])
print(dp[-1][-1])

### FIXED CODE ###

H,N,*AB = map(int, open(0).read().split())
dp = [0]+[10**8]*H
for n in range(N):
  A,B = AB[2*n:2*(n+1)]
  for h in range(1,H+1): dp[h] = min(dp[h],dp[max(0,h-A)]+B)
print(dp[-1])
### BUGGY CODE ###

n = int(input())
s = str(input())
r = []
g = []
b = []


for x in range(n):
    if s[x] == 'R':
        r.append(x+1)
        continue
    if s[x] == 'G':
        g.append(x+1)
        continue
    if s[x] == 'B':
        b.append(x+1)
        continue

def count(x,y,z):
    c = 0
    for i in x:
        for j in y:
            if i > j: continue 
            for k in z:
                if j > k: continue 
                if j - i != k - j:
                    c += 1
    return c

ans = 0
ans += count(r,g,b)
ans += count(r,b,g)
ans += count(b,r,g)
ans += count(b,g,r)
ans += count(g,r,b)
ans += count(g,b,r)

print(ans)


### FIXED CODE ###


def main():
    n = int(input())
    s = str(input())
    cnt = 0
    r = s.count('R')
    g = s.count('G')
    b = s.count('B')

    for i in range(n):
        for j in range(i,n):
            if i == j:
                continue
            k = 2 * j - i
            if k > len(s) - 1:
                continue
            if s[i] == s[j] or s[j] == s[k] or s[k] == s[i]:
                continue

            cnt +=1

    all = r * g * b
    print(all - cnt) 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

def main():
    N=int(input())
    A=[int(x) for x in input().split()]
    Q=int(input())
    BC=[list(map(int, input().split())) for _ in range(Q)]
    for bc in BC:
        A=[bc[1] if x==bc[0] else x for x in A]
        print(sum(A))
    return

if __name__=='__main__':
    main()


### FIXED CODE ###

def main():
    N=int(input())
    l=[0]*10**5
    sm=0
    A=map(int, input().split())
    for a in A:
        l[a-1]+=1
        sm+=a
    Q=int(input())
    BC=[list(map(int,input().split())) for _ in range(Q)]
    for bc in BC:
        cnt=l[bc[0]-1]
        l[bc[0]-1]=0
        l[bc[1]-1]+=cnt
        sm=sm-bc[0]*cnt+bc[1]*cnt
        print(sm)
    return

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

n = int(input())
l = list(map(int,input().split(" ")))
l.sort()
cnt = 0 
def search(arr,target,start,last):
    while(last > start):
        mid = (last + start)//2
        #print("start:",start, "last:" ,last, "mid:",mid)
        if arr[mid] < target:
            start = mid + 1 
        else:
            last = mid 
    return start

for i in range(0,n-2):
    a = l[i]
    for j in range(i+1,n-1):
        b = l[j]
        target = a + b 
        f1 = search(l,target,j+1,n)
        #print(f1)
        cnt+= f1 - j -1
print(cnt)

### FIXED CODE ###

n = int(input())
l = list(map(int,input().split(" ")))
l.sort()
cnt = 0 
import bisect
for i in range(0,n-2):
    a = l[i]
    for j in range(i+1,n-1):
        b = l[j]
        target = a + b 
  #      print("#",a,b)
        f1 = bisect.bisect_left(l,target,j+1,n)
        cnt+= f1 - 1- j
   #     print("cnt: ",cnt)
print(cnt)
### BUGGY CODE ###

#n,W=map(int, input().split())
s=input()
t=input()
ns=len(s)
nt=len(t)
dp=[[(0,[]) for j in range(ns+1)] for i in range(nt+1)]
    
for i in range(1,nt+1):
    for j in range(1,ns+1):
        if t[i-1]==s[j-1]:
            dp[i][j]=(dp[i-1][j-1][0]+1,dp[i-1][j-1][1]+[i-1])
        else:
            a,b=dp[i-1][j],dp[i][j-1]
            c=max(a[0],b[0])
            if c==a[0]:
                dp[i][j]=a
            else:
                dp[i][j]=b
    
ans=[]
for i in dp[-1][-1][-1]:
    ans.append(t[i])
print(''.join(ans))

### FIXED CODE ###

#n,W=map(int, input().split())
s=input()
t=input()
ns=len(s)
nt=len(t)
dp=[[0 for j in range(ns+1)] for i in range(nt+1)]
    
for i in range(1,nt+1):
    for j in range(1,ns+1):
        if t[i-1]==s[j-1]:
            dp[i][j]=dp[i-1][j-1]+1
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])

cnt=dp[-1][-1]
ans=[]
ct,cs=nt,ns
while cnt>0:
    while dp[ct][cs]==dp[ct-1][cs] and ct>0:
        ct-=1
        
    while dp[ct][cs]==dp[ct][cs-1] and cs>0:
        cs-=1

    ans.append(t[ct-1])
    cnt-=1
    #print(ct,cs,t[ct-1])
    ct-=1
    cs-=1

print(''.join(ans[::-1]))
### BUGGY CODE ###

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

for i in range(1,n+1):
    print(a.count(i))

### FIXED CODE ###

import collections
n = int(input())
a = list(map(int,input().split()))
c = collections.Counter(a)
for i in range(1,n+1):
    print(c[i])
### BUGGY CODE ###

n , k = map(int, input().split())
a = list(map(int,input().split()))
a.sort()

N = 1000000007

def combi(n,r,N):
    if n<r or n<0 or r<0:
        ans = 0
        return ans
    if n==r:
        ans = 1
        return ans
    r= min(r, n-r)
    ans = f[n]*rf[r]*rf[n-r]%N
    return ans

f = [0]*(n+1)
f[1]=1

for i in range(2,n+1):
    f[i] = f[i-1]*i

rf = [0]*(n+1)

for i in range(1,n+1):
    rf[i] = pow(f[i],N-2,N)

max_sum=0
min_sum=0

for i in range(k-1,n):
    max_sum+=a[i]*combi(i,k-1,N)
    max_sum%=N
for i in range(n-k+1):
    min_sum+=a[i]*combi(n-i-1,k-1,N)
    min_sum%=N
if max_sum-min_sum<0:
    max_sum+=N
print(max_sum-min_sum)


### FIXED CODE ###

n , k = map(int, input().split())
a = list(map(int,input().split()))
a.sort()

MOD = 1000000007

factorial = [1]
inverse = [1]
for i in range(1, n+2):
    factorial.append(factorial[-1] * i % MOD)
    inverse.append(pow(factorial[-1], MOD - 2, MOD))

def combi(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % MOD

max_sum=0
min_sum=0

for i in range(k-1,n):
    t = combi(i,k-1)
    max_sum+=a[i]*t
    max_sum%=MOD
    min_sum+=a[n-i-1]*t
    min_sum%=MOD
if max_sum-min_sum<0:
    max_sum+=MOD
print(max_sum-min_sum)
### BUGGY CODE ###

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


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
a = sorted(a)
ans = 1
for i in range(n):
         ans *= a[i]
         if ans == 0:
                  print(ans)
                  exit()
         elif ans > (10 ** 18):
                  print(-1)
                  exit()
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
N,K = map(int,input().split())
LR = [tuple(map(int,input().split())) for i in range(K)]
LR.sort()
MOD = 998244353

arr = []
for l,r in LR:
    for i in range(l,r+1):
        arr.append(i)

from functools import lru_cache
@lru_cache(maxsize=10**8)
def rec(n):
    if n==0: return 1
    ret = 0
    for a in arr:
        if n-a < 0: break
        ret += rec(n-a)
        ret %= MOD
    return ret

print(rec(N-1))

### FIXED CODE ###

import sys
input = sys.stdin.readline
N,K = map(int,input().split())
LR = [tuple(map(int,input().split())) for i in range(K)]
MOD = 998244353

dp = [1]
cumdp = [0,1]
for i in range(1,N):
    tmp = 0
    for l,r in LR:
        if i-l+1 <= 0: continue
        tmp += cumdp[i-l+1] - cumdp[max(0,i-r)]
    tmp %= MOD
    dp.append(tmp)
    cumdp.append((cumdp[-1] + tmp) % MOD)
print(dp[-1])
### BUGGY CODE ###

def findlcs(x, y):
    dp = [0]*(len(y)+1)

    for i in range(len(x)):
        tmp = dp[:]
        for j in range(len(y)):
            if x[i] == y[j]:
                dp[j+1] = tmp[j] + 1
            else:
                dp[j+1] = max(dp[j+1], dp[j])

    return dp[len(y)]


q = int(input())
for k in range(q):
    X = input()
    Y = input()
    print(findlcs(X, Y))

### FIXED CODE ###

def findlcs(x, y):
    dp = [0]*(len(y)+1)

    for c in x:
        tmp = dp[:]
        for j in range(len(y)):
            if c == y[j]:
                dp[j+1] = tmp[j] + 1
            elif dp[j+1] < dp[j]:
                dp[j+1] = dp[j]

    return dp[-1]


q = int(input())
for k in range(q):
    X = input()
    Y = input()
    print(findlcs(X, Y))
### BUGGY CODE ###

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


### FIXED CODE ###

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

if __name__ == '__main__':
    import sys
    input = sys.stdin.readline
    n, k = map(int, input().split())
    hs = list(map(int, input().split()))
    if n <= k+1:
        print(abs(hs[0]-hs[-1]))
        exit()
    ans_list = [0]*n
    for i in range(1,k+1):
        ans_list[-i] = abs(hs[-1] - hs[-i])
    for i in range(k+1,n+1):
        hs_i = hs[-i]
        ans_list[-i] = min([abs(hs_i-hs[x])+ans_list[x] for x in range(1-i,k+1-i)])
    print(ans_list[0])


### FIXED CODE ###

if __name__ == '__main__':
    import sys
    input = sys.stdin.readline
    n, k = map(int, input().split())
    hs = list(map(int, input().split()))
    if n <= k+1:
        print(abs(hs[0]-hs[-1]))
        exit()
    ans_list = [0]*n
    last_hs = hs[-1]
    for i in range(1,k+2):
        ans_list[-i] = abs(last_hs - hs[-i])
    for i in range(k+2,n+1):
        hs_i = hs[-i]
        ans_list[-i] = min([abs(hs_i-x)+y for x,y in zip(hs[1-i:k+1-i],ans_list[1-i:k+1-i])])
    print(ans_list[0])
### BUGGY CODE ###

import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

h, w, k = na()
s = nsn(h)

ans = inf
for bits in range(2 ** (h - 1)):
    binf = "{0:b}".format(bits)
    res = sum([int(b) for b in binf])
    divcnt = res + 1
    cnt = [0] * divcnt
    flag = True
    j = 0
    while j < w:
        cur = 0
        for i in range(h):
            if (s[i][j] == '1'):
                cnt[cur] += 1
            if bits >> i & 1:
                cur += 1
        if max(cnt) > k:
            if flag:
                res = inf
                break
            res += 1
            for i in range(divcnt):
                cnt[i] = 0
            flag = True
        else:
            flag = False
            j += 1
    ans = min(ans, res)

print(ans)

### FIXED CODE ###

import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

h, w, k = na()
s = nsn(h)

ans = inf
for bits in range(2 ** (h - 1)):
    binf = "{0:b}".format(bits)
    res = sum([int(b) for b in binf])
    divcnt = res + 1
    cnt = [0] * divcnt
    flag = True
    j = 0
    while j < w:
        cur = 0
        for i in range(h):
            if (s[i][j] == '1'):
                cnt[cur] += 1
            if bits >> i & 1:
                cur += 1
        if max(cnt) > k:
            if flag:
                res = inf
                break
            res += 1
            for i in range(divcnt):
                cnt[i] = 0
            flag = True
        else:
            flag = False
            j += 1
    ans = min(ans, res)

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

# ΣnCiが高速に計算できればいいがNがでかい -> なんかΣncrでググったら高速化できるらしい?
# なんかi=0 -> i=nで2^nになるらしい。これは繰り返し二乗法でいけそう

# 最終的にΣnCi(i=1, i<=n) - nCa - nCaができればいい

# なぜか手持ちのライブラリがことごとくダメ

n, a, b = map(int, input().split())
mod = 10**9 + 7


def rep(i, n):
    if n == 0:
        return 1
    if n % 2 == 0:
        tmp = rep(i, n // 2) % mod
        return tmp * tmp % mod
    else:
        return i * rep(i, n - 1) % mod


# なぜかうまくいかない
# def ncr(n, r):
#     res = 1
#     for i in range(1, r + 1):
#         res = res * (n - i + 1) // i
#         res %= mod
#     for i in range(2, r + 1):
#         res *= rep(i, mod - 2)
#         res %= mod
#     return res

# なぜかうまくいかない
# def cmb(n, r, mod):
#     if (r < 0 or r > n):
#         return 0
#     g1 = [1, 1]  # 元テーブル
#     g2 = [1, 1]  #逆元テーブル
#     inverse = [0, 1]  #逆元テーブル計算用テーブル
#     N = 10**6  # なんでだろうね
#     for i in range(2, N + 1):
#         g1.append((g1[-1] * i) % mod)
#         inverse.append((-inverse[mod % i] * (mod // i)) % mod)
#         g2.append((g2[-1] * inverse[-1]) % mod)
#     return g1[n] * g2[r] * g2[n - r] % mod


# なぜかうまくいく
def nCrMod(n, r, p):
    ret = 1
    # 分子
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret %= p
    # 分母
    for i in range(2, r + 1):
        # ret //= i なんかこれがおかしい（なんでだろうね）
        ret *= rep(i, p - 2)  # なぜかここでやらないと駄目だった
        ret %= p
    # ret = repMod(ret, p - 2, p) # なぜかここでやると駄目だった
    return ret % p


ans = (rep(2, n) - 1 - nCrMod(n, a, mod) - nCrMod(n, b, mod)) % mod  # なぜかうまくいく
# ans = (rep(2, n) - 1 - ncr(n, a) - ncr(n, b)) % mod なぜかうまくいかない
# ans = (rep(2, n) - 1 - cmb(n, a, mod) - cmb(n, b, mod)) % mod なぜかうまくいかない
while ans < 0:
    ans += mod
print(ans)


### FIXED CODE ###

# ncrかなと思うが実験すると1 3 6 10 15 21みたいなのが出てくる
# あらかじめN個作っとくんだけどこれ間に合うん？
# 無理ですね はい  解説

# 愚直にみればそれぞれ選ぶか選ばないかで2通りがn回続く
# a,bの2数も含むとすると、すなわち、2^(n) - 1（かならず1本は選ぶので）。これは繰り返し二乗法で解く。
# ここからa,bを考えたものを引く。具体的にはnCr(n, a) mod p とnCr(n, b) mod pを引く。
# nCr mod pで間に合わんやんけと思って諦めたけどよくよく読んだら条件はa = min(n, 2*10^5)なので間に合うやんけ
# nCrの式変形で分母と分子をそれぞれ作ってやるっていう愚直なやつでもいけるんじゃねこれ

n, a, b = map(int, input().split())
MOD = 10**9 + 7


# 繰り返し二乗法
def repMod(a, n, p):
    if n == 1:
        return a % p
    if n % 2 == 1:
        return a * repMod(a, n - 1, p) % p
    ret = repMod(a, n // 2, p) % p
    return (ret * ret) % p


all_comb = repMod(2, n, MOD)
# nCr = n!/(r!(n-r)!) ゆえ ((n-r+1) * (n-r+2) * .. * n)/(1*2*3*..*r)
# これがr = min(n, 2*10^5)なので愚直にやっても間に合う


def nCrMod(n, r, p):
    ret = 1
    # 分子
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret %= p
    # 分母
    for i in range(2, r + 1):
        # ret //= i なんかこれがおかしい（なんでだろうね）
        ret *= repMod(i, p - 2, p)  # なぜかここでやらないと駄目だった
        ret %= p
    # ret = repMod(ret, p - 2, p) # なぜかここでやると駄目だった
    return ret % p


print((all_comb - nCrMod(n, a, MOD) - nCrMod(n, b, MOD) - 1) % MOD)
### BUGGY CODE ###

N = int(input())
A = input().split()
for q in range(int(input())):
    B,C = input().split()
    A = list(map(lambda x: x.replace(B,C),A))
    print(sum(map(lambda x: int(x),A)))

### FIXED CODE ###

import numpy as np

N = int(input())
A = np.array([int(a) for a in input().split()])
ans = sum(A)
lst = np.zeros(10**5+1)
for a in A:
    lst[a] += 1
   
for q in range(int(input())):
    B,C = map(int,input().split())
    ans += (C - B) * lst[B]
    print(int(ans))
    lst[C] += lst[B]
    lst[B] = 0
### BUGGY CODE ###

import math
X = int(input())

for a in range(1, 1500):
    a4 = a**4
    a3 = a**3
    a2 = a**2
    for b in range(-1, 1500):
        an = (a-b)*(a4 + (a3)*b + (a2)*(b**2) + a*(b**3) + b**4)

        if an == X:
            print(a, b)
            exit()


### FIXED CODE ###

import math
X = int(input())

for a in range(1, 1500):
    a4 = a**4
    a3 = a**3
    a2 = a**2
    for b in range(-1500, 1500):
        an = (a-b)*(a4 + (a3)*b + (a2)*(b**2) + a*(b**3) + b**4)
        if an < 0:
            break

        if an == X:
            print(a, b)
            exit()
### BUGGY CODE ###

n=int(input())
array=[]
array+=map(int,input().split())
flag=0
flag2=0
s=1
for m in range(len(array)):
    if array[m]==0:
        flag=1
        break
    s=s*array[m]

if flag==1:
    print("0")
elif s>10**18:
    print("-1")
else:print(s)



### FIXED CODE ###

n=int(input())
array=[]
array+=map(int,input().split())
flag=0
flag2=0
s=1
for m in range(len(array)):
    if array[m]==0:
        flag=1
        break
    s=s*array[m]
    if s>10**18:
        flag2=1
        break
flag3=0
if flag==1:
    print("0")
elif flag2==1:
    for i in range(m,len(array)):
        if array[i]==0:
            flag3=1
            print("0")
    if flag3==0:
        print("-1")

else:print(s)
### BUGGY CODE ###

import copy
S=input()
sx=list(str(S))
s=list(map(int,sx))
#print(s)
cnt=0
while(1):
    t=copy.deepcopy(s) 
    for i in range(len(s)-1):
        if s[i]+s[i+1]==1:
            s.pop(i+1)
            s.pop(i)
            cnt+=2
            break
    if s==t:
        break
print(cnt)

### FIXED CODE ###

s=input()
a=s.count('0')
b=s.count('1')
print(min(a,b)*2)