Harryxun/stf_run huggingface dataset:
from fractions import gcd
N, M=map(int, input().split())
A=list(map(int, input().split()))
#最上公倍数
def lcm(x, y):
  return (x * y) //gcd(x, y)
#最小半公倍数
def half_lcm(a,b):
  X=lcm(a,b)//2
  return X

S=[0]*(N-1)
now=A[0]
for i in range(1,N):
  now=lcm(now, A[i])
  S[i-1]=now
  
kobai=S[-1]
hkobai=kobai//2
print(int(1+(M-hkobai)//kobai))




#6*(2.5,7.5,12.5,17.5
#10*(1.5,4.5,7.5,10.5)
#15,45,75,105
#4 (2.5,)
#10(1,)

### FIXED CODE ###

N,M=map(int, input().split())
from collections import defaultdict
A=list(map(int, input().split()))
B=[]
import math
def lcm(x, y):
    return (x * y) // math.gcd(x, y)
# a 偶数
twos=0
D=defaultdict(int)
for i in range(N):
    B.append(A[i]//2)
    a=A[i]
    now=0
    while a%2==0:
        a//=2
        now+=1
    D[now]+=1
    twos=max(twos, now)
if len(set(D.values()))!=1:
    print(0)
    exit()
now=1
for i in range(N):
    now=lcm(now, B[i])

# 1.5 * 3 2*5
from math import ceil
ans=M//(now*pow(2,twos))+1
#res=now+now%(2**twos)
ans=ceil(M//now/2)
#if M-res>0:
#    ans-=int((M-res)//now/(2**twos))

print(ans)
#!/usr/bin/env python3
import sys
from fractions import gcd
input = sys.stdin.readline
 
class DisjointSparseTable:
    def __init__(self, a):
        # Identity element
        self.e = 0
        self.level = (len(a) - 1).bit_length()
        self.size = 2**self.level
        self.table = [[self.e] * self.size for _ in range(self.level)]
        # Set bottom first
        for i, item in enumerate(a):
            self.table[-1][i] = item
        self.build()
 
    def build(self):
        for i in range(1, self.level):
            step = 2**i
            lv = self.level - 1 - i
            for mid in range(step, self.size, step*2):
                if mid - step >= self.n:
                    continue
                # Forward
                val = self.e 
                for j in range(step):
                    val = gcd(self.table[-1][mid + j], val)
                    self.table[lv][mid + j] = val
                # Backward
                val = self.e
                for j in range(step):
                    val = gcd(self.table[-1][mid - 1 - j], val)
                    self.table[lv][mid - 1 - j] = val
 
    # Returns f[l:r)
    def query(self, l, r):
        if l == r:
            return self.e
        elif l == r - 1:
            return self.table[-1][l]
        lv = self.level - (l ^ r-1).bit_length()
        return gcd(self.table[lv][l], self.table[lv][r-1])
 
 
if __name__ == "__main__":
    n = int(input())
    a = [int(item) for item in input().split()]
    DST = DisjointSparseTable(a)
    ans = 0
    for i in range(0, n):
        ans = max(ans, gcd(DST.query(0, i), DST.query(i+1, n)))
    print(ans)

### FIXED CODE ###

n = int(input())
a = [int(item) for item in input().split()]

def gcd(a,b):
 while b!=0:
   a,b=b,a%b
 return a

if n == 2:
    print(max(a))
    exit()

bad_id = 0
max_div = 1
for j in range(10):
    if j == 5:
        bad_id == 0
        a.reverse()
    bid = bad_id
    init = False
    for i, item in enumerate(a):
        if i == bid:
            continue
        if not init:
            val = item
            div = val
            init = True
        else:
            val = gcd(div, item)
            if val != div:
                bad_id = i
                div = val
    max_div = max(div, max_div)
    
print(max_div)
p, q, r = map(int, input().split())
# 文字列の入力
# s = input()
# 出力


print("{} {}".format(min(p+q, q+r, r+p), s))


### FIXED CODE ###

p, q, r = map(int, input().split())
# 文字列の入力
# s = input()
# 出力
 
 
print("{}".format(min(p+q, q+r, r+p)))
S = "redcoder"

ans = 0

ALEN = (len(A))
 
B = list(A)
 
 
 
B_re =  list(reversed(B))
 
ans = 0
 
 
for i in range(ALEN):
    if B[i] != B_re[i]:
        ans = ans+1
    
if ans　% 2 == 0:
    print(ans//2)
elif ans %2 != 0:
    print((ans//2) +1)
elif ans == 0:
    print(0)

### FIXED CODE ###

S = input()

ans = 0

ALEN = (len(S))
 
B = list(S)
 
 
 
B_re =  list(reversed(B))
 
ans = 0
 

 
for i in range(ALEN):
  if B[i] != B_re[i]:
        ans = ans+1
    
if ans % 2 == 0:
    print(ans//2)
elif ans %2 != 0:
    print((ans//2) +1)
elif ans == 0:
    print(0)
n=int(input())
x=list(map(int,list(input())))
def popcount(x):
  ret=0
  while x:
    if x%2==1:ret+=1
    x//=2
  return ret
def f(x):
  ret=0
  while x:
    x%=popcount(x)
    ret+=1
  return ret
from collections import Counter
xpop=Counter(x)[1]
xint=sum([pow(2,n-i-1)*y for i,y in enumerate(x)])
for i,y in enumerate(x):
  if y:
    yint=xint-pow(2,n-i-1)
    ypop=xpop-1
  else:
    yint=xint+pow(2,n-i-1)
    ypop=xpop+1
  #print(yint,ypop)
  yint%=ypop
  print(f(yint)+1)


### FIXED CODE ###

n=int(input())
x=input()
import sys
sys.setrecursionlimit(10**7)
if n==1:
  print(0 if x=='1' else 1)
  exit()
def pc(x):
  a=bin(x)[2:]
  return a.count('1')
def func(x):
  if x==0:
    return 0
  else:
    return func(x%pc(x))+1
pcx=x.count('1')
if pcx==0:
  for _ in range(n):
    print(1)
else:
  x0,x1=0,0
  for i in range(n):
    if x[i]=='1':
      if pcx!=1:
        x0+=pow(2,n-1-i,pcx-1)
        x0%=pcx-1
      x1+=pow(2,n-1-i,pcx+1)
      x1%=pcx+1
  for i in range(n):
    ans=0
    if x[i]=='1':
      if pcx==1:
        print(0)
      else:
        xx=x0-pow(2,n-1-i,pcx-1)
        xx%=pcx-1
        print(func(xx)+1)
    else:
      xx=x1+pow(2,n-1-i,pcx+1)
      xx%=pcx+1
      print(func(xx)+1)
def gcd(a,b):
    if b>a:
        a,b=b,a
    while b:
        a,b=b, a%b
    return a

def f(a,b,N):
    
    def cur(n):
        if n<0: return -1
        if memo[n]!=-1: return memo[n]
        tmp=[]
        memo[n]=max(cur(n-a[i])+b[i] for i in range(3))
        return memo[n]
    
    memo=[0]+[-1]*(N)
    return cur(N)

import sys
N=int(input())

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

N=f(A,B,N)
N=f(B,A,N)
print(N)

### FIXED CODE ###

def f(a,b,N):

    tmpa,tmpb=[],[]
    for i in range(3):
        if a[i]<b[i]:
            tmpa.append(a[i])
            tmpb.append(b[i])
    a,b=tmpa,tmpb

    if len(a)==0: return N
    elif len(a)==1: return (N//a[0])*b[0]+N%a[0]

    elif len(a)==2:
        if a[0]<a[1]: a,b=a[::-1],b[::-1]

        i,ans=0,N
        while i*a[0]<=N:
            j=(N-i*a[0])//a[1]
            ans=max(ans,i*b[0]+j*b[1]+(N-i*a[0]-j*a[1]))
            i+=1
        return ans

    else:
        memo=[i for i in range(N+1)]

        for i in range(1,N+1):
            tmp=[]
            for j in range(len(a)):
                if i-a[j]>=0: tmp.append(memo[i-a[j]]+b[j])
            if tmp!=[]: memo[i]=max(tmp)
        return memo[N]

import sys
N=int(input())

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

N=f(A,B,N)
N=f(B,A,N)
print(N)
def per(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r=n-r
    return g1[n] * g2[r] % mod

mod = 10**9+7 #出力の制限
N = 10**4
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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 )


n=int(input())
A=[1]
for i in range(1,n-1):
  A.append(A[-1]*(i+1)+per(i,i,mod))
X=list(map(int,input().split()))
Y=[X[1]-X[0]]
for i in range(2,n):
  Y.append(X[i]-X[i-1])
ans=0
for i in range(n-1):
  if n-2-i==0:
    ans=ans+A[i]*Y[i]
  else:
    ans=(ans+A[i]*per(n-1,n-2-i,mod)*Y[i])%(10**9+7)
print(ans%mod)

### FIXED CODE ###

n=int(input())
x=list(map(int,input().split()))
a=1
B=[1,1]
mod=10**9+7
for i in range(2,n):
  a=a*i%mod
  B.append(pow(i,mod-2,mod))
d=[0]*(n-1)
for i in range(n-1):
  d[i]=x[i+1]-x[i]
D=[d[-1]]
for i in range(n-2):
  D.append(D[-1]+d[-2-i])
D=D[::-1]
ans=0
for i in range(n-1):
  ans=(ans+D[i]*a*B[i+1])%mod
print(ans)
while True:
    h,w = map(int,input().split())
    def bw(x):
        if x % 2 == 0:
            print((x//2)*('#.'))
        elif x % 2 == 1:
            print((x//2)*('#.')+'#')
    def wb(x):
        if x % 2 == 0:
            print((x//2)*('.#'))
        elif x % 2 == 0:
            print((x//2)*('.#')+'.')
    for i in range(h+1):
        if i % 2 == 0:
            bw(w)
        else:
            wb(w)
    print(i)
            

### FIXED CODE ###

while True:
    H,W = map(int,input().split())
    if H == W == 0:
        break
    a = '#.'
    b = '#'
    c = '.#'
    d = '.'

    def bw(n):
        if n % 2 == 0:
            print((n//2)*a)
        else:
            print((n//2)*a + b)

    def wb(n):
        if n % 2 == 0:
            print((n//2)*c)
        else:
            print((n//2)*c + d)

    for i in range(1,H + 1):
        if i % 2 == 0:
            wb(W)
        else:
            bw(W)
    print()
A, B = map(int, input().split())
if A < B:
    print("<")
elif A==B:
    print("=")
else:
    print(">")

### FIXED CODE ###

X, Y = map(str, input().split())
print("<" if X < Y else ">" if X > Y else "=")
X, A = map(int, input().split())

if X < A: print(0)
else print()10


### FIXED CODE ###

X, A = map(int, input().split())

if X < A: print(0)
else: print(10)
history = set([])


import sympy

def func(n):
    if n == 1:
        return 
    l = sympy.divisors(n)
    for i in sorted(l[1:]):
        if i in history:
            continue
        if len(sympy.factorint(i)) > 1:
            continue
        print(i, n)
        history.add(i)
        _ = n // i
        func(_)
        break
    return

N = int(input())
if N == 0:
    print(0)
elif N == 1:
    print(1)
else:
    func(N)
    print(len(history))

### FIXED CODE ###

history = set([])

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

def func(n):
    if n == 1:
        return 
    l = make_divisors(n)
    for i in sorted(l[1:]):
        if i in history:
            continue
        if len(factorization(i)) > 1:
            continue
        history.add(i)
        _ = n // i
        func(_)
        break
    return

N = int(input())
if N == 0:
    print(0)
elif N == 1:
    print(0)
else:
    func(N)
    print(len(history))
import collections
N = int(input())
A = list(map(int,input().split()))
CA = collections.Counter(A)
S = 0
for i in range(CA.values()):
    S += int(i*(i-1)/2)
for k in range(N):
    print(S - A.count(A[k]) + 1)

### FIXED CODE ###

import collections
N = int(input())
A = list(map(int,input().split()))
CA = collections.Counter(A)
S = 0
for i in CA.values():
    S += i*(i-1)//2
for x in A:
    print(S - CA[x] + 1)
wa = 0
ac = 0
ac_list = []
if m==0:
    print(0,0)
else:
    for i in range(m-1:
        p,s = input().split()
        if s=='WA':
            wa += 1
        elif ac_list.count(p) ==0:
            ac_list.append(p)
            ac += 1
        else:
            pass

### FIXED CODE ###

n,m = map(int, input().split())
wa = 0
ac_list = {'AC':{}, 'WA':{}}
if m==0:
    print(0,0)
else:
    for i in range(m):
        p,s = input().split()
        ac_list[s][p] = ac_list[s].get(p, 0) + 1* int(not(p in ac_list['AC'].keys()))
    kyotu_key = list(set(ac_list['AC'].keys()) & set(ac_list['WA'].keys()))
    wa_list = [ac_list['WA'][p] for p in kyotu_key]
    print(len(ac_list['AC'].keys()), sum(wa_list))
N, M = [int(x) for x in input().split()]
links = [tuple(map(int, input().split())) for _ in range(M)]
S, T = [int(x) for x in input().split()]

d = {}
for x, y in links:
    if x in d:
        d[x][0].add(y)
    else:
        d[x] = [{y}, False]

def next_node(start):
    history = set()
    for s in start:
        if s in d:
            history |= d[s][0]
    return history

history = {S}
s = 1
while True:
    for _ in range(3):
        history = next_node(history)
    if T in history:
        print(s)
        break
    for h in tuple(history):
        if h in d and d[h][1]:
            history.remove(h)
        else:
            d[h][1] = True
    if len(history) == 0:
        print(-1)
        break
    s += 1


### FIXED CODE ###

N, M = [int(x) for x in input().split()]
links = [tuple(map(int, input().split())) for _ in range(M)]
S, T = [int(x) for x in input().split()]

d = {}
for x, y in links:
    if x in d:
        d[x][0].add(y)
    else:
        d[x] = [{y}, False]

def next_node(start):
    history = set()
    for s in start:
        if s in d:
            history |= d[s][0]
    return history

history = {S}
s = 1
while True:
    for _ in range(3):
        history = next_node(history)
    if T in history:
        print(s)
        break
    for h in tuple(history):
        if h not in d or d[h][1]:
            history.remove(h)
        else:
            d[h][1] = True
    if len(history) == 0:
        print(-1)
        break
    s += 1
ab_a = sorted(ab)
ab_b = sorted(ab, key= lambda x:x[1])

way = [0] * (n + 1)
for a, b in ab:
    if a == 1:
        way[b] += 1
    if b == 1:
        way[a] += 1
    if a == n:
        way[b] += 1
    if b == n:
        way[a] += 1
if 2 in way:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

### FIXED CODE ###

n, m = [int(item) for item in input().split()]
ab = [[int(item) for item in input().split()] for _ in range(m)]

way = [0] * (n + 1)
for a, b in ab:
    if a == 1:
        way[b] += 1
    if b == 1:
        way[a] += 1
    if a == n:
        way[b] += 1
    if b == n:
        way[a] += 1
if 2 in way:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
N = int(input())
A = list(map(int,input().split()))
memo = {}
for a in A:
    if a in memo:
        memo[a] += 1
    else:
        memo[a] = 1
memo_sorted = sorted(memo.items(), key=lambda x:-x[1])
memo = []
for a,b in memo_sorted:
    memo.append([a,b])

for key,val in enumerate(memo):
    val_1, val_2 = val
    if val_2 <= 1:
        continue
    else:
        if val_2%2 == 1:
            memo[key][1] = 1
        elif val_2%2 == 0:
            if key < N-1:
                memo[key+1][1] -= 1
            memo[key][1] = 1
ans = 0
for a,b in memo:
    ans += b
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
memo = {}
for a in A:
    if a in memo:
        memo[a] += 1
    else:
        memo[a] = 1
memo_sorted = sorted(memo.items(), key=lambda x:-x[1])
memo = []
for a,b in memo_sorted:
    memo.append([a,b])

for key,val in enumerate(memo):
    val_1, val_2 = val
    if val_2 <= 1:
        continue
    else:
        if val_2%2 == 1:
            memo[key][1] = 1
        elif val_2%2 == 0:
            if key < len(memo)-1:
                memo[key+1][1] -= 1
                memo[key][1] = 1
            else:
                memo[key][1] = 0
ans = 0
for a,b in memo:
    ans += b
print(ans)
while True:
    n,m = map(int,raw_input().split(' '))

### FIXED CODE ###

while True:
    try:
        n,m = list(map(int,input().split()))
        if n == 0 and m == 0:
            break
        amari = n % m
        yasai = list(map(int,input().split())) 
        yasai.sort()

        s = 0
        for i in range(n):
            if (i+1) % m > 0:
                s += yasai[-i-1]
        print(s)
    except:
        pass
import math
ans=0
c=0
N = int(input())
A = [int(i) for i in input().split()] 
L=[1]*N
R=[1]*N
L[0]=1
L[1]=A[0]
R[N-1]=1
R[N-2]=A[N-1]
for i in range(2,N):
    L[i]=math.gcd(L[i-1],A[i-1])
    R[N-i-1]=math.gcd(R[N-i],A[N-i])
for i in range(N):
    if i==0 or i==N-1:
        c=max(L[i],R[i])
        if c>=ans:
            ans=c
    else:
        c=math.gcd(L[i],R[i])
        if c>=ans:
            ans=c
print(ans)

### FIXED CODE ###

from fractions import gcd
n = int(input())
a = list(map(int,input().split()))
left,right = [a[0]]+[0]*(n-1),[0]*(n-1)+[a[n-1]]
arr = [0]*n
for i in range(0,n-1):
  left[i+1] = gcd(left[i],a[i+1])
  right[n-2-i] = gcd(right[n-1-i],a[n-2-i])
arr[0] = right[1]
arr[n-1] = left[n-2]
for i in range(1,n-1):
  arr[i] = gcd(left[i-1],right[i+1])
print(max(arr))
i = 0
n = (int)raw_input()
while !n:
  i = i+1
  print 'Case {0}: {1}'.format(i,n)
  n = (int)raw_input()

### FIXED CODE ###

n = input()
i = 1
while n != 0:
  print "Case %d: %d" % (i, n)
  n = input()
  i += 1;
N,M = map(int,input().split())
PY = [[int(py) for py in input().split()] for _ in range(M)]

for i in range(1,M+1):
    PY[i-1].append(i)

PY.sort(key=lambda x:x[1])

count = [1 for _ in range(M)]

ans = []

for cell in PY:
    row = '{0:06d}'.format(cell[0]) + '{0:06d}'.format(count[cell[0]])
    ans.append([row,cell[2]])
    count[cell[0]] += 1


ans.sort(key=lambda x:x[1])

for row in ans:
    print(row[0])

### FIXED CODE ###

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

for i in range(1,M+1):
    PY[i-1].append(i)

PY.sort(key=lambda x:x[1])

count = [1 for _ in range(N)]

ans = []

for cell in PY:
    row = '{0:06d}'.format(cell[0]) + '{0:06d}'.format(count[cell[0]-1])
    ans.append([row,cell[2]])
    count[cell[0]-1] += 1


ans.sort(key=lambda x:x[1])

for row in ans:
    print(row[0])
n,c = map(int,input().split())
d = [[int(i) for i in input().split()] for _ in range(c)]
lc = [[int(i)-1 for i in input().split()] for _ in range(n)]

ans = float("inf")

for c0 in range(c):
  for c1 in range(c):
    if c0 == c1: continue
    for c2 in range(c):
      if c0 == c2 or c1 == c2: continue
      tmp = 0
      c = [c0,c1,c2]
      for y in range(n):
        for x in range(n):
          if lc[y][x] != c[(y+x)%3]: tmp += d[lc[y][x]][c[(y+x)%3]]
      ans = min(ans, tmp)
print(ans)

### FIXED CODE ###

#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#A
def A():
    return

#B
def B():
    return

#C
def C():
    n = II()
    dp = [inf for i in range(n + 1)]
    ans = [1]
    x = 6
    while x <= n:
        ans.append(x)
        x = x * 6
    x = 9
    while x <= n:
        ans.append(x)
        x = x * 9
    ans.sort()
    for i in ans:
        dp[i] = 1
    for i in range(1, n + 1):
        if not i in ans:
            a = bisect.bisect_left(ans, i)
            for k in range(a):
                #print(i,ans[k], a)
                dp[i] = min(dp[i - ans[k]] + 1, dp[i])
    print(dp[n])

    return

#D
def D():
    n, c = LI()
    D = LIR(c)
    C = LIR_(n)
    CL = list(itertools.permutations(range(c), 3))
    ans = inf
    amari0 = [0 for i in range(30)]
    amari1 = amari0[::1]
    amari2 = amari0[::1]
    for y in range(n):
        for x in range(n):
            amari = (x + y) % 3
            if amari == 0:
                amari0[C[y][x]] += 1
            if amari == 1:
                amari1[C[y][x]] += 1
            if amari == 2:
                amari2[C[y][x]] += 1
    for c0, c1, c2 in CL:
        ansb = 0
        for i in range(c):
            ansb += D[i][c0] * amari0[i]
            ansb += D[i][c1] * amari1[i]
            ansb += D[i][c2] * amari2[i]
        ans = min(ans, ansb)

            
    print(ans)

    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    D()
s=input()
k=int(input())

count_1=0
while s[0]=='1':
  count_1+=1
  s=s.lstrip('1')
if count_1>=k:
  print('1')
else:
  print(s[0])


### FIXED CODE ###

s=input()
k=int(input())

count_1=0
while s!='':
  if s[0]=='1':
    count_1+=1
    s=s[1:]
  else:
    break
if count_1>=k:
  print('1')
else:
  print(s[0])
A = int(input())
B = int(input())

print((A-1)*(B-1))

### FIXED CODE ###

A,B = map(int, input().split())

print((A-1)*(B-1))
n = input()
num = []
num = input().split(" ")

t = 0 
 a=0 
while True: 
  num2=[] 
  for i in num: 
    if not (int(i)%2): 
    	a =1 
        break 
    num2.append(int(i)%2) 
    num = num2 
    t+=1 
    if a==1: 
       print(t) 
       break 

### FIXED CODE ###

n = input()
num = []
num = input().split(" ")
 
t = 0 
a=0 
while True: 
  num2=[] 
  for i in num: 
    if not int(i)%2==0:
      a =1
      break
    num2.append(int(i)/2)
  num = num2
  if a==1: 
     print(t) 
     break
  t+=1
def main():
    import math
    import collections
    N = int(input())

    # def cmb(n, r, mod):
    #     if (r < 0 or r > n):
    #         return 0
    #     r = min(r, n-r)
    #     return g1[n] * g2[r] * g2[n-r] % mod

    mod = 10**9+7
    # g1 = [1, 1]  # 元テーブル
    # g2 = [1, 1]  # 逆元テーブル
    # inverse = [0, 1]  # 逆元テーブル計算用テーブル

    # 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)

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

    # d = collections.defaultdict(int)
    d = collections.defaultdict(set)
    # d2 = collections.defaultdict(int)
    i = 0
    ab = []
    for a, b in AB:
        g = math.gcd(a, b)
        a = a // g
        b = b // g
        # d[(a, b)] += 1
        if a > 0 and b < 0:
            a = -a
            b = -b
        d[(a, b)].add(i)
        ab.append((a, b))
        i += 1

    ans = 0
    r = set()

    dd = [1]
    for i in range(1, N):
        dd.append(dd[i-1]*2 % mod)

    r = set()
    ans = 1
    for (a, b) in d:
        if (a, b) in r:
            continue
        l1 = len(d[(a, b)])
        tmp = dd[l1]
        s = set()
        if (-b, a) in d:
            s |= d[(-b, a)]
        if (b, -a) in d:
            s |= d[(b, -a)]
        l2 = len(s)
        if l2:
            ans *= tmp + dd[l2] - 1
            N -= l1 + l2
            ans %= mod

            r.add((-b, a))
            r.add((b, -a))
        else:
            continue
    if N:
        ans *= dd[N-1]*2
    ans -= 1

    print(ans % mod)


main()


### FIXED CODE ###

def main():
    import math
    import collections
    N = int(input())

    mod = 10**9+7
    AB = [tuple(map(int, input().split())) for i in range(N)]

    d = collections.defaultdict(set)
    i = 0
    ans2 = 0
    for a, b in AB:
        if a == 0 and b == 0:
            N -= 1
            ans2 += 1
            continue
        g = math.gcd(a, b)
        if g != 0:
            a = a // g
            b = b // g

        d[(a, b)].add(i)
        i += 1

    ans = 0
    r = set()

    dd = [1]
    for i in range(1, N+1):
        dd.append(dd[i-1]*2 % mod)

    r = set()
    ans = 1
    for a, b in d:
        if (a, b) in r:
            continue
        s1 = d[(a, b)]
        if (-a, -b) in d:
            s1 |= d[(-a, -b)]
        l1 = len(s1)
        r.add((-a, -b))
        if l1:
            s2 = set()
            if (-b, a) in d:
                s2 |= d[(-b, a)]
            if (b, -a) in d:
                s2 |= d[(b, -a)]
            s2 -= s1
            l2 = len(s2)
            if l2:
                ans *= dd[l1] + dd[l2] - 1
                N -= l1 + l2
                ans %= mod
                r.add((-b, a))
                r.add((b, -a))
            else:
                continue
    if N:
        ans *= dd[N]
    ans += ans2
    ans -= 1
    print(ans % mod)


main()