Harryxun/stf_run huggingface dataset:
from collections import defaultdict
from heapq import heappop, heappush
N = int(input())
A = list(map(int, input().split()))

d = defaultdict(int)
for a in A:
    d[a] += 1

T = []
for a in list(set(A)):
    T.append([a, d[a]])

M = len(T)
T = sorted(T)
i = 1
flag = True
while T[0][1] - 1 > 0:
    if T[i][1] > 1:
        T[i][1] -= 1
        flag = False
        T[0][1] -= 1
    i += 1
    if i == M:
        if flag:
            break
        i = 1
        flag = True

if T[0][1] > 1:
    if T[0][1]%2:
        print(M)
    else:
        print(M-1)
else:
    for i in range(M):
        if T[i][1] > 2:
            if T[i][1]%2:
                T[i][1] = 1
            else:
                T[i][1] = 2
    cnt = 0
    for i in range(M):
        if T[0][1] == 2:
            cnt += 1
    if cnt%2:
        print(M-1)
    else:
        print(M)


### FIXED CODE ###

N = int(input())
A = set(list(map(int, input().split())))
if len(A)%2:
    print(len(A))
else:
    print(len(A)-1)
n = input()
s = ""
for i in range(1,n+1):
    if(i%3==0 or i%10==3):
        s += " " + str(i)
print(s)


### FIXED CODE ###

n = int(input())
print(" ",end="")
print(*[i for i in range(1,1+n) if i%3==0 or'3' in str(i)])
a,b,c=input().split()
print(["NO","YES"][a[-1]==b[0] and b[-1]==c[1]])

### FIXED CODE ###

a,b,c=input().split()
print(["NO","YES"][a[-1]==b[0] and b[-1]==c[0]])
N = int(input())

lst_W = []
for i in range(N):
    lst_W.extend(input().split())

ans = "Yes"

for i in range(N - 1):
    if (lst_W[i])[-1:] != (lst_W[i+1])[:1]:
        ans = "No"
        break

if len(lst_W) != len(set(lst_W)):
    #ans = "No"

print(ans)

### FIXED CODE ###


N = int(input())

lst_W = []
for i in range(N):
    lst_W.extend(input().split())

ans = "Yes"

for i in range(N - 1):
    if (lst_W[i])[-1:] != (lst_W[i+1])[:1]:
        ans = "No"
        break

if len(lst_W) != len(set(lst_W)):
    ans = "No"

print(ans)
import math
a, b = map(int, input().split())
#a,bの最小公倍数
def lcm(a, b):
  return a * b // math.gcd (a, b)
print(lcm(a, b))

### FIXED CODE ###

import fractions
a, b = map(int, input().split())
print(a * b // fractions.gcd(a, b))
score = [1999,1799,1599,1399,1199,999,799,599]
ranks = [   1,   2,   3,   4,   5,  6,  7,  8]

x = int(input())
i = 0

while(x <= score[i]):
      i += 1

print(ranks[i-1])


### FIXED CODE ###

score = [1800,1600,1400,1200,1000, 800, 600, 400]
ranks = [   1,   2,   3,   4,   5,   6,   7,   8]

x = int(input())
i = 0

while(x < score[i]):
      i += 1

print(ranks[i])
n = int(input())
x = list(range(n))
y = list(range(n))
h = list(range(n))

for i in range(n):
  x[i], y[i], h[i] = map(int, input().split())

flag=0
i = 0
while(flag==0 and i < 101):
  j = 0
  while(flag==0 and j < 101):
    ans_h = 0
    for k in range(n):
      if h[k] == 0:
        if k == n-1 and ans_h != 0:
          ans_x = i
          ans_y = j
          flag=1
          break
        else:
          pass
      if ans_h == 0:
        ans_h = abs(i-x[k])+abs(j-y[k])+h[k]
      elif abs(i-x[k])+abs(j-y[k])+h[k] != ans_h:
        break
      if ans_h != 0 and k == n-1:
        ans_x = i
        ans_y = j
        flag=1
        break
    j+=1
  i+=1

print(ans_x, ans_y, ans_h)

### FIXED CODE ###

n = int(input())
x = list(range(n))
y = list(range(n))
h = list(range(n))

for i in range(n):
  x[i], y[i], h[i] = map(int, input().split())
  if h[i] != 0:
    X = x[i]
    Y = y[i]
    H = h[i]

flag=0
i = 0
while(flag==0 and i < 101):
  j = 0
  while(flag==0 and j < 101):
    ans_h = abs(i-X)+abs(j-Y)+H
    for k in range(n):
      h_ = max(ans_h-abs(i-x[k])-abs(j-y[k]), 0)
      if h_ != h[k]:
        break
      if k == n-1:
        ans_x = i
        ans_y = j
        flag=1
        break
    j+=1
  i+=1

print(ans_x, ans_y, ans_h)
n = int(input())
w = {}
for _ in range(n):
  	s = input()
    w[s] = w.get(s, 0) + 1
ans = sorted(i for i, j in w.items() if j == max(w.values()))
for i in ans:
    print(i)


### FIXED CODE ###

n = int(input())
s = list(input() for _ in range(n))
s.sort()
now = s[0]
ans = [s[0],]
cnt = 0
m_cnt = 0

for i in range(n):
    word = s[i]
    if word == now:
        cnt +=1
        if cnt > m_cnt:
            ans = [word,]
            m_cnt = cnt
        elif cnt == m_cnt:
            ans.append(word)
    else:
        cnt = 1
        now = word
        if cnt > m_cnt:
            ans = [word,]
            m_cnt = cnt
        elif cnt == m_cnt:
            ans.append(word)

for k in sorted(ans):
    print(k)
l, m, n = map(int,input().split())
a = [[0 for i in range(l)]for j in range(m)]
b = [[0 for i in range(m)]for j in range(n)]
c = [[0 for i in range(l)]for j in range(n)]

for i in range(l):
 for j in range(n):
  for k in range(m):
   c[i][j] += a[i][m] * b[m][j]
 print(" ".join([str(x) for x in c[i]]))

### FIXED CODE ###

l, m, n = map(int,input().split())
a = [[0 for i in range(m)] for i in range(l)]
b = [[0 for i in range(n)] for i in range(m)]
c = [[0 for i in range(n)] for i in range(l)]

for i in range(l):
 a[i] = [int(x) for x in input().split()]

for i in range(m):
 b[i] = [int(x) for x in input().split()]

for i in range(l):
 for j in range(n):
  for k in range(m):
   c[i][j] += (a[i][k] * b[k][j])
 print(" ".join([str(x) for x in c[i]]))
import sys
import numpy as np
import bisect
s = input()
t = input()



count = 0
s_len = len(s)
s_list = np.zeros(len(s))
t_list = []*len(t)
indexes = []

for i in range(26):
  
  indexes.append([j for j, x in enumerate(s) if x == chr(i + ord('a')) ])
  

for i,k in enumerate(t):

  index = indexes[ord(k)-97]
  
  if len(indexes) == 0:
    print(-1)
    sys.exit(0)
  else:
    t_list.insert(i,index)
    


pre = -1
for i in range(len(t)):
  
  #high = [j  for j in t_list[i] if j > pre]
  high = bisect.bisect_left(t_list[i], pre) 

  if high >= len(t_list[i]):
    
    count += s_len - pre  + t_list[i][0]
    pre = t_list[i][0] 
  else:
    
    count += t_list[i][high] - pre 
    pre = t_list[i][high]

print(count)

### FIXED CODE ###

import sys
import numpy as np
import bisect
s = input()
t = input()



count = 0
s_len = len(s)
s_list = np.zeros(len(s))
t_list = []*len(t)
indexes = []

for i in range(26):
  
  indexes.append([j for j, x in enumerate(s) if x == chr(i + ord('a')) ])
  


for i,k in enumerate(t):

  index = indexes[ord(k)-ord('a')]
  
  if len(index) == 0:
    print(-1)
    sys.exit(0)
  else:
    t_list.insert(i,index)
    


pre = -1
for i in range(len(t)):
  
  #high = [j  for j in t_list[i] if j > pre]
  high = bisect.bisect_left(t_list[i], pre+1) 

  if high >= len(t_list[i]):
    
    count += s_len - pre  + t_list[i][0]
    pre = t_list[i][0] 
  else:
    
    count += t_list[i][high] - pre 
    pre = t_list[i][high]

print(count)
s = input()
t = input()
     
if s == t[:len(s)]:
	if t[-1] in 'abcdefghijklmnopqrstuvwxyz'
		print('Yes')
        exit(0)
        
print('No')

### FIXED CODE ###

s = input()
t = input()
     
if s == t[:len(s)]:
	if t[-1] in 'abcdefghijklmnopqrstuvwxyz':
		print('Yes')
		exit(0)       

print('No')
a, b, c = [int(x) for x in input().split(" ")]

if a + b + (a*B)**(1/2) < c:
  print(Yes)
else:
  print(No)

### FIXED CODE ###

a, b, c = [int(x) for x in input().split(" ")]

if a*a+b*b+c*c > 2*a*b+2*b*c+2*c*a and c-a-b > 0:
  print("Yes")
else:
  print("No")
import numpy as np
import sys
input = sys.stdin.readline
def main():
    r,c,k=map(int,input().split())
    a=[list(map(int,input().split())) for _ in range(k)]
    dp=np.array([[[0,0,0,0,0]for _ in range(c+1)]for _ in range(r+1)])
    b=[[0 for _ in range(c+1)] for _ in range(r+1)]
    for x,y,z in a:
        b[x][y]=z
    for i in range(1,r+1):
        for j in range(1,c+1):
            v=b[i][j]
            if b==0:
                dp[i][j][0]=max(dp[i][j-1][0],dp[i-1][j][0],dp[i-1][j][1],dp[i-1][j][2],dp[i-1][j][3])
                dp[i][j][1]=dp[i][j-1][1]
                dp[i][j][2]=dp[i][j-1][2]
                dp[i][j][3]=dp[i][j-1][3]
            else:
                dp[i][j][0]=max(dp[i][j-1][0],dp[i-1][j][0],dp[i-1][j][1],dp[i-1][j][2],dp[i-1][j][3])
                dp[i][j][1]=max(dp[i][j-1][1],dp[i][j-1][0]+v,dp[i-1][j][0]+v,dp[i-1][j][1]+v,dp[i-1][j][2]+v,dp[i-1][j][3]+v)
                dp[i][j][2]=max(dp[i][j-1][2],dp[i][j-1][1]+v)
                dp[i][j][3]=max(dp[i][j-1][3],dp[i][j-1][2]+v)
    print(max(dp[i][j]))

if __name__ == "__main__":
    main()


### FIXED CODE ###

r,c,k=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(k)]
dp=[[[0 for _ in range(c+1)]for _ in range(r+1)]for _ in range(5)]
for x,y,z in a:
    dp[4][x][y]=z
for i in range(1,r+1):
    for j in range(1,c+1):
        v=dp[4][i][j]
        dp[0][i][j]=max(dp[0][i][j-1],dp[0][i-1][j],dp[1][i-1][j],dp[2][i-1][j],dp[3][i-1][j])
        dp[1][i][j]=max(dp[1][i][j-1],dp[0][i][j-1]+v,dp[0][i-1][j]+v,dp[1][i-1][j]+v,dp[2][i-1][j]+v,dp[3][i-1][j]+v)
        dp[2][i][j]=max(dp[2][i][j-1],dp[1][i][j-1]+v)
        dp[3][i][j]=max(dp[3][i][j-1],dp[2][i][j-1]+v)
print(max([dp[i][r][c] for i in range(4)]))
import math
N = int(input())

k = 0
if N%2 ==0:
  n = N//2
  i = 1
  while n　>= 5**i :
    k += math.floor(n /(5**i))
    i += 1

print(k)    

### FIXED CODE ###

import math
N = int(input())

k = 0
if N%2 ==0:
  n = N//2
  i = 5
  while n >= i :
    k += n //i
    i *= 5

print(k)
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a
 
#targetまでの素数の数
import math
def sieve_of_eratosthenes2(target):
    dest = int(math.sqrt(target))
    target_list = [i for i in range(2, dest+1) if target%i==0]
    prime_num = 0
 
    while True:
        num_min = min(target_list)
        if num_min > dest:
            prime_num += len(target_list)
            break
        prime_num += 1        
        target_list = [i for i in target_list if i%num_min!=0]
        if target_list==[]:
            break
 
    return prime_num   
 
a, b = map(int, input().split())
gcd = xgcd(a, b)
if gcd == 1:
    print(1)
else:
    ans = sieve_of_eratosthenes2(gcd)    
    print(ans+1)

### FIXED CODE ###

def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a


import random
def is_prime(q, k=50):
    q = abs(q)
    if q == 2:
        return True
    if q < 2 or q % 2 == 0:
        return False

    d = (q - 1) >> 1
    while d & 1 == 0:
        d >>= 1
    for i in range(k):
        a = random.randint(1, q - 1)
        t = d
        y = pow(a, t, q)
        while t != q - 1 and y != 1 and y != q - 1:
            y = pow(y, 2, q)
            t <<= 1
        if y != q - 1 and t & 1 == 0:
            return False
    return True

def prime_num(target):
    ra = 2
    prime = 0
    while target>1:
        if target%ra == 0:
            prime += 1
            while target%ra==0:
                target = target//ra
            if is_prime(target):
                prime += 1
                break
        if ra == 2:
            ra += 1
        else:
            ra += 2
    return prime   
        
a, b = map(int, input().split())
gcd = xgcd(a, b)
if gcd == 1:
    print(1)
elif is_prime(gcd):
    print(2)
else:
    ans = prime_num(gcd)    
    print(ans+1)
N=int(input())
A=[int(i) for i in input().split()]
A.sort()
miss=0
if N%2==0:
    for i in range(int(N/2)):
        if miss==1:
            break
        for j in range(2):
            if A[0]==2*i+1:
                A.pop(0)
            else:
                miss=1
                break
    if miss==1:
        print(0)
    else:
        print(int((2**int(N/2))%(10e9+7)))

if N%2==1:
    if not 0 in A:
        miss=1
    else:
        A.pop(0)
    for i in range(int((N-1)/2)):
        if miss==1:
            break
        for j in range(2):
            if A[0]==2*i+2:
                A.pop(0)
            else:
                miss=1
                break
    if miss==1:
        print(0)
    else:
        print(int((2**int((N-1)/2))%(10e9+7)))



### FIXED CODE ###

N=int(input())
A=[int(i) for i in input().split()]
A.sort()
miss=0

if N%2==0:
    for i in range(int(N/2)):    
        if miss==1:
            break
        for j in range(2):
            if A[0]==2*i+1:
                A.pop(0)
            else:
                miss=1
                break
                
    if miss==1:
        print(0)
    else:
        print(int((2**int(N/2))%(10**9+7)))

else:
    if A[0]!=0:
        miss=1
        A.pop(0)
    else:
        A.pop(0)
    for i in range(int((N-1)/2)):
        if miss==1:
            break
        for j in range(2):
            if A[0]==2*i+2:
                A.pop(0)
            else:
                miss=1
                break
                
    if miss==1:
        print(0)
    else:
        print(int((2**int((N-1)/2))%(10**9+7)))
from functools import lru_cache
import sys
sys.setrecursionlimit(10 ** 6)

p = None


@lru_cache
def rec(i, j):
    if i < 0 or j < 0:
        return 0.0
    if i == 0 and j == 0:
        return 1.0
    return rec(i - 1, j) * (1 - p[i - 1]) + rec(i - 1, j - 1) * p[i - 1]


def main():
    N = int(input())
    global p
    p = list(map(float, input().split()))
    ans = 0
    for i in range(N // 2 + 1, N + 1):
        ans += rec(N, i)
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N = int(input())
    p = list(map(float, input().split()))
    dp = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
    p_mul = 1
    dp[0][0] = 1
    for i in range(1, N + 1):
        p_mul *= (1-p[i-1])
        dp[i][0] = p_mul
    for i in range(1, N+1):
        for j in range(1, N+1):
            dp[i][j] = dp[i - 1][j] * \
                (1 - p[i - 1]) + dp[i - 1][j - 1] * p[i - 1]
    print(sum(dp[N][N//2+1:]))


if __name__ == "__main__":
    main()
import statistics
import math

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

B = []
C = []
D = []
E = []
ureshimi = []
k = 0
l = 0

sumA = sum(A)
sumBC = sum(A[0:2])
sumDE = sum(A) - sumBC

s = 0
mannnaka = 0

for i in range(N-2):
    s += A[i]
    if i == N - 3:
        mannnaka = N - 3
    elif s + A[i + 1] > sumA / 2:
        mannnaka = i
        break



saisho = max(0, mannnaka - 7)
saigo = min(N - 4, mannnaka + 5)

sumBC = sum(A[0:saisho + 2])
sumDE = sum(A) - sumBC

print(saisho, saigo)

for i in range(saisho, saigo):
    BC = A[0 : i + 2]
    s = sum(A[0 : k])
    for j in range(k, i + 2):
        s += BC[j]
        if j == i + 1:
            k = j 
            B = BC[0 : j ]
            C = BC[j  : N - i]
            break
        elif s + BC[j + 1] > sumBC / 2:
            k = j
            if BC[j + 1] / 2 >= sumBC / 2 - s:
                B = BC[0 : j + 1]
                C = BC[j + 1 : i + 2]
            else:
                B = BC[0 : j + 2]
                C = BC[j + 2 : i + 2]
            break
    print(i, k)
    sumBC += A[i + 2]
    DE = A[i + 2 : N + 1]
    s = sum(DE[0:l - i + 1 ])
    for j in range(l - i + 1 , N - i - 2):
        if j == N - i - 3:
            l = j + i 
            D = DE[0 : j ]
            E = DE[j  : N - i]
            break
        elif s + DE[j ] > sumDE / 2:
            l = j + i
            if DE[j ] / 2 >= sumDE / 2 - s:
                D = DE[0 : j ]
                E = DE[j : N - i]
            else:
                D = DE[0 : j + 1]
                E = DE[j + 1 : N - i]
            break
        s += DE[j]
    sumDE -= A[i + 2]

    ureshimi.append(max(sum(B), sum(C), sum(D), sum(E)) - min(sum(B), sum(C), sum(D), sum(E)))



print(min(ureshimi))

### FIXED CODE ###

import statistics
import math

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


ureshimi = []
k = 0
l = 2

B = 0
C = 0
D = 0
E = 0

sumBC = sum(A[0:2])
sumDE = sum(A) - sumBC

for i in range(2, N - 1):
    for j in range(k, i):
        if j == i - 1:
            k = j
            C = sumBC - B
            break
        elif B + A[j] >= sumBC / 2:
            if sumBC / 2 - B  > A[j] / 2:
                B += A[j]
                k = j + 1
                C = sumBC - B
                break
            else:
                k = j
                C = sumBC - B
                break
        B += A[j]
    for j in range(l, N):
        if j == N - 1:
            l = j
            E = sumDE - D
            break
        elif D + A[j] >= sumDE / 2:
            if sumDE / 2 - D > A[j] / 2:
                D += A[j]
                l = j + 1
                E = sumDE - D
                break
            else:
                l = j
                E = sumDE - D
                break
        D += A[j]
    ureshimi.append(max([B, C, D, E]) - min([B, C, D, E]))
    sumBC += A[i]
    sumDE -= A[i]
    D -= A[i]
        

print(min(ureshimi))
def solv():
    n = int(input())
    A = list(map(int,input().split()))
    B = list(map(int,input().split()))
    ans = 0

    for i in range(n):
        x = A[i] + A[i+1]
        ans += min(x,B[i])
        A[i+1] = min(A[i+1],max(x-B[i+1],0))
    return print(ans)

solv()


### FIXED CODE ###

def solv():
    n = int(input())
    A = list(map(int,input().split()))
    B = list(map(int,input().split()))
    ans = 0

    for i in range(n):
        x = A[i] + A[i+1]
        ans += min(x,B[i])
        A[i+1] = min(A[i+1],max(x-B[i],0))
    return print(ans)

solv()
A = int(A)
B = int(B)
ans = 0
while B > (A-1)*ans + A :
  ans += 1
print(ans)

### FIXED CODE ###

A,B = map(int,input().split())
ans = 0
if B>1:
    while B>(A-1)*ans+A:
        ans+=1
    print(ans+1)
else:
    print(ans)
n = input()
if n < 1200: print('ABC')
elif n < 2800: print('ARC')
else: print('AGC')

### FIXED CODE ###

n = int(input())
if n < 1200: print('ABC')
elif n < 2800: print('ARC')
else: print('AGC')
N, M = map(int, input().split())
num = [input().split() for y in range(N)]


def check(target):
    if not len(target) == N:
        return False
    for x, y in num:
        if not target[x-1] == y:
            return False
    return True


for i in range(1000):
    if check(str(i)):
        print(i)
        exit()
        
print(-1)


### FIXED CODE ###

N, M = map(int, input().split())
num = [input().split() for y in range(M)]


def check(target):
    if not len(target) == N:
        return False
    for x, y in num:
        if not target[int(x)-1] == y:
            return False
    return True


for i in range(1000):
    if check(str(i)):
        print(i)
        exit()

print(-1)
n = input()
a,b = divmod(n,1000)
print(b)

### FIXED CODE ###

n = int(input())
a,b = divmod(n,1000)
if b == 0:
    print(0)
else:

    print(1000-b)
N,X=map(int,input().split())
def a(n):
    if n==0:
        return 1
    else:
        return a(n-1)*2+3
def p(n):
    if n==0:
        return 1
    else:
        return p(n-1)*2+1
def f(n,x):
    if x==0:
        return 0
    if 0<x<=a(n-1)+1:
        return f(n-1,x-1)
    if x==a(n-1)+2:
        return 1+p(n-1)
    if a(n-1)+2<x<=a(n-1)*2+2:
        return 1+p(n-1)+f(n-1,x-a(n-1)-2)
    if x==2*a(n-1)+3:
        return p(n)
print(f(N,X))

### FIXED CODE ###

N, X = map(int, input().split())
a,p=[1],[1] 
for i in range(N):
    a.append(a[i] * 2 + 3)
    p.append(p[i] * 2 + 1)
def f(N,X): #X<=0やX>a_Nを許容し解説本文から簡略化
    if N == 0:
        return 0 if X <= 0 else 1
    elif X <= 1 + a[N-1]:
        return f(N-1, X-1)
    else:
        return p[N-1] + 1 + f(N-1, X-2-a[N-1])
print(f(N, X))
S=list(input())
N=len(S)
ans=0
i=0
while len(S)>0:
  if S[i]==0 and S[i+1]==1 or S[i]==1 and S[i+1]==0:
    S.remove(S[i:i+2])
    ans+=1
  else:
    ans=ans
    i+=1
print(ans)

### FIXED CODE ###

S=input()
N=len(S)
a=S.count('0')
b=S.count('1')
t=min(a,b)
print(2*t)
import collections

def gcd(a,b):
  if b==0:
    return a
  else:
    return gcd(b,a%b)

mod=10**9+7
n=int(input())
dic=collections.defaultdict(0)
cnt=0
for _ in range(n):
  a,b=map(int,input().split())
  if a!=0 and b!=0:
    g=gcd(abs(a),abs(b))
    if (a>0 and b>0) or (a<0 and b<0):
      dic[(abs(a)//g,abs(b)//g)]+=1
    elif (a<0 and b>0) or (a>0 and b<0):
      dic[(-abs(a)//g,abs(b)//g)]+=1
  else:
    if a==0 and b==0:
      cnt+=1
    elif a==0:
      dic[(1,0)]+=1
    elif b==0:
      dic[(0,1)]+=1
ans=1
s=set()
for a,b in dic.keys():
  if (a,b) in s:
    continue
  s.add((a,b))
  if a!=0 and b!=0:
    if a>0:
      if (-b,a) in dic:
        s.add((-b,a))
        cnt1=dic[(a,b)]
        cnt2=dic[(-b,a)]
        ans*=(pow(2,cnt1,mod)+pow(2,cnt2,mod)-1)%mod
        ans%=mod
      else:
        ans*=pow(2,dic[(a,b)])
        ans%=mod
    elif a<0:
      if (b,-a) in dic:
        s.add((b,-a))
        cnt1=dic[(a,b)]
        cnt2=dic[(b,-a)]
        ans*=(pow(2,cnt1,mod)+pow(2,cnt2,mod)-1)%mod
        ans%=mod
      else:
        ans*=pow(2,dic[(a,b)],mod)
        ans%=mod
  else:
    if (b,a) in dic:
      s.add((b,a))
      cnt1=dic[(a,b)]
      cnt2=dic[(b,a)]
      ans*=(pow(2,cnt1,mod)+pow(2,cnt2,mod)-1)%mod
      ans%=mod
    else:
      ans*=pow(2,dic[(a,b)],mod)
      ans%=mod
print((ans+cnt-1)%mod)

### FIXED CODE ###

def gcd(a,b):
  if b==0:
    return a
  else:
    return gcd(b,a%b)

mod=10**9+7
n=int(input())
dic={}
cnt=0
for _ in range(n):
  a,b=map(int,input().split())
  if a!=0 and b!=0:
    g=gcd(abs(a),abs(b))
    if (a>0 and b>0) or (a<0 and b<0):
      if (abs(a)//g,abs(b)//g) not in dic:
        dic[(abs(a)//g,abs(b)//g)]=1
      else:
        dic[(abs(a)//g,abs(b)//g)]+=1
    elif (a<0 and b>0) or (a>0 and b<0):
      if (-abs(a)//g,abs(b)//g) not in dic:
        dic[(-abs(a)//g,abs(b)//g)]=1
      else:
        dic[(-abs(a)//g,abs(b)//g)]+=1
  else:
    if a==0 and b==0:
      cnt+=1
    elif a==0:
      if (1,0) not in dic:
        dic[(1,0)]=1
      else:
        dic[(1,0)]+=1
    elif b==0:
      if (0,1) not in dic:
        dic[(0,1)]=1
      else:
        dic[(0,1)]+=1
ans=1
s=set()
for a,b in dic.keys():
  if (a,b) in s:
    continue
  s.add((a,b))
  if a!=0 and b!=0:
    if a>0:
      if (-b,a) in dic:
        s.add((-b,a))
        cnt1=dic[(a,b)]
        cnt2=dic[(-b,a)]
        ans*=(pow(2,cnt1,mod)+pow(2,cnt2,mod)-1)%mod
        ans%=mod
      else:
        ans*=pow(2,dic[(a,b)])
        ans%=mod
    elif a<0:
      if (b,-a) in dic:
        s.add((b,-a))
        cnt1=dic[(a,b)]
        cnt2=dic[(b,-a)]
        ans*=(pow(2,cnt1,mod)+pow(2,cnt2,mod)-1)%mod
        ans%=mod
      else:
        ans*=pow(2,dic[(a,b)],mod)
        ans%=mod
  else:
    if (b,a) in dic:
      s.add((b,a))
      cnt1=dic[(a,b)]
      cnt2=dic[(b,a)]
      ans*=(pow(2,cnt1,mod)+pow(2,cnt2,mod)-1)%mod
      ans%=mod
    else:
      ans*=pow(2,dic[(a,b)],mod)
      ans%=mod
print((ans+cnt-1)%mod)
A = int(input())
B = int(input())
if A % 3 == 0 or B % 3 == 0 or (A + B) % 3 == 0:
  print("Possible")
else:
  print("Impossible")

### FIXED CODE ###

A= (input().split())
if int(A[0]) % 3 == 0 or int(A[1]) % 3 == 0 or (int(A[0]) + int(A[1])) % 3 == 0:
    print("Possible")
else:
    print("Impossible")
print(int(input())*2)

### FIXED CODE ###

a,b=map(int,input().split())
print((a-1)*(b-1))
N, K = map(int, input().split())
S = list(map(int, input()))

Z = [j for j, s in enumerate(S) if (j > 0 and s == 0 and S[j] != S[j-1]) or (j == 0 and s == 0)] + [N]
Y = [j for j, s in enumerate(S) if (j > 0 and s == 1 and S[j] != S[j-1]) or (j == 0 and s == 1)]
result = 0
if len(Z) <= K:
  print(N)
else:
  for i in range(len(Z)-K):
    if i == 0:
      result = Z[i+K]
    else:
      result = max(result, Z[i+K] - Y[i if Y[0] < Z[0] else i-1])
    print(result)

### FIXED CODE ###

input_ = list(map(int,input().split()))
x = input_[0]
y = input_[1]
point = max(x,y)
if point == x:
  x -= 1
else:
    y -= 1
point += max(x,y)
print(point)
import math

#入力
a,b,x = map(int, input().split())

if a*b*a/2 < x:
    if a == 1 and b == 1 and x == 1:
        print(0)
    else:
        c = 2*x/(a*a) - b
        d = a*b/(b-c)
        print(90-math.degrees(math.atan(d/b)))
else:
    c = (2*x)/(a*b)
    print(90 - math.degrees(math.atan(c/b)))


### FIXED CODE ###

import math

#入力
a,b,x = map(int, input().split())

if a*b*a/2 < x:
    c = 2*x/(a*a) - b
    if b == c:
        print(0)
    else:
        d = a*b/(b-c)
        print(90-math.degrees(math.atan(d/b)))
else:
    c = (2*x)/(a*b)
    print(90 - math.degrees(math.atan(c/b)))