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

from heapq import heappush, heappop

INF = float('inf')

def dijkstra(n, G, s):
    dist = [INF] * n
    dist[s] = 0
    h = []
    heappush(h, (0, s))

    while h:
        # 使っていない頂点のうち、現時点で最も距離の近いものを選びvとする
        d, v = heappop(h)
        if dist[v] < d:
            continue
        # vから到達可能な頂点について、距離が短くなれば更新
        for b, cost in G[v]:
            if dist[b] > dist[v] + cost:
                dist[b] = dist[v] + cost
                heappush(h, (dist[b], b))
    return dist

n, x, y = map(int, input().split())

g = [[] for i in range(n)]

for i in range(n-1):
    g[i].append((i+1, 1))
    g[i+1].append((i, 1))

g[x-1].append((y-1, 1))
g[y-1].append((x-1, 1))

ans = [0] * n

for i in range(n):
    for d in dijkstra(n, g, i):
        ans[d] += 1

for item in ans[1:]:
    print(item // 2)



### FIXED CODE ###

n, x, y = map(int, input().split())
ans = [0 for i in range(n)]
x -= 1
y -= 1
for i in range(n):
    for j in range(i+1, n):
        cand1 = j - i
        cand2 = abs(x - i) + 1 + abs(y-j)
        ans[min(cand1, cand2)] += 1

for item in ans[1:]:
    print(item)
### BUGGY CODE ###

from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
#import math
#import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
#ts=time.time()
sys.setrecursionlimit(10**6)
#input=sys.stdin.readline
show_flg=False
show_flg=True


def gcd(a,b):
    a,b=max(a,b),min(a,b)
    if a%b==0:
        return b
    rt=gcd(a%b,b)
    return rt

a,b=MI()
g=gcd(a,b)
ans=set()
ans.add(1)



for i in range(2,int(g**0.5)+2):
    if g%i==0:
        ans.add(i)
        while g%i==0:
            g//=i

for i in range(2,g+1):
    if g%i==0:
        ans.add(i)
    
    
print(len(ans))


### FIXED CODE ###

from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
#import math
#import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
#ts=time.time()
sys.setrecursionlimit(10**6)
#input=sys.stdin.readline
show_flg=False
show_flg=True


def gcd(a,b):
    a,b=max(a,b),min(a,b)
    if a%b==0:
        return b
    rt=gcd(a%b,b)
    return rt

a,b=MI()
g=gcd(a,b)
og=g
ans=set()
ans.add(1)



for i in range(2,int(g**0.5)+2):
    if g%i==0:
        ans.add(i)
        while g%i==0:
            g//=i

x=len(ans)
if g>int(og**0.5) and og!=1:
    x+=1
    
print(x)
### BUGGY CODE ###

S = input()
T = input()


for i in range(len(S)):
    S_ch = [j for j, x in enumerate(S) if x == S[i]]
    T_ch = [j for j, x in enumerate(T) if x == T[i]]
    if S_ch != T_ch:
        print('No')
        exit()

print('Yes')


### FIXED CODE ###

S = input()
T = input()

string = ''

for i in range(len(S)):
    if S[i] not in string:
        S_ch = [j for j, x in enumerate(S) if x == S[i]]
        T_ch = [j for j, x in enumerate(T) if x == T[i]]
        string += S[i]
        if S_ch != T_ch:
            print('No')
            exit()

print('Yes')
### BUGGY CODE ###

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

# from itertools import combinations

# comb = list(combinations([i for i in range(N)],2))

# cnt=0
# for i in comb:
#     if Agents[i[0]] + Agents[i[1]] == abs(i[0] - i[1]):
#         print(i[0],i[1])
#         cnt+=1

# print(cnt)
cnt=0

for i in range(0,N):
    k=Agents[i]-(i+1)
    if k<i:
        k=i+1
    for j in range(k,N):
        if Agents[i]+Agents[j]==abs(i-j):
            # print(i,j,Agents[i],Agents[j])
            cnt+=1

print(cnt)


### FIXED CODE ###

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


##Miss 1
# from itertools import combinations

# comb = list(combinations([i for i in range(N)],2))

# cnt=0
# for i in comb:
#     if Agents[i[0]] + Agents[i[1]] == abs(i[0] - i[1]):
#         print(i[0],i[1])
#         cnt+=1

# print(cnt)

# Miss 2
# for i in range(0,N):
#     k=Agents[i]-(i+1)
#     if k<i:
#         k=i+1
#     for j in range(k,N):
#         if Agents[i]+Agents[j]==abs(i-j):
#             # print(i,j,Agents[i],Agents[j])
#             cnt+=1


L={}
for i in range(N):
    s = i+1 + Agents[i] 
    if s in L:
        L[s]+=1
    else:
        L[s]=1

R={}
for j in range(N):
    s= j+1 - Agents[j]
    if s in R:
        R[s]+=1
    else:
        R[s]=1
cnt=0

for key,value in L.items():
    cnt += R.get(key,0) * value
# for key,value in L.items():
#     for key2,value2 in R.items():
#         if int(key) < int(key2) and value == value2:
#             cnt+=1


print(cnt)
### BUGGY CODE ###

from collections import deque



def bfs(maze, visited, queue, H, W):
    count = 0
    while queue:
        y, x = queue.popleft()
        for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y + i, x + j
            if -1 < new_y < H and -1 < new_x < W:
                if maze[new_y][new_x] == "." and visited[new_y][new_x] == -1:
                    visited[new_y][new_x] = visited[y][x] + 1
                    queue.append([new_y, new_x])

    ans = -1
    for i in range(H):
        for j in range(W):
            ans = max(ans,visited[i][j])
    return ans

H, W = map(int,input().split())

maze = [input() for i in range(H)]
visited = [[-1] * W for i in range(H)]

queue = deque([])
for i in range(H):
    for j in range(W):
        if maze[i][j] == "#":
            visited[i][j] = 0
            queue.append([i, j])

print(bfs(maze, visited, queue, H, W))

### FIXED CODE ###

from collections import deque



def bfs(maze, visited, queue, H, W):
    count = 0
    while queue:
        y, x = queue.popleft()
        for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y + i, x + j
            if -1 < new_y < H and -1 < new_x < W:
                if maze[new_y][new_x] == "." and visited[new_y][new_x] == -1:
                    visited[new_y][new_x] = visited[y][x] + 1
                    queue.append([new_y, new_x])

    ans = -1
    for i in range(H):
        for j in range(W):
            ans = max(ans,visited[i][j])
    return ans

H, W = map(int,input().split())

maze = [input() for i in range(H)]
visited = [[-1] * W for i in range(H)]

queue = deque([])
for i in range(H):
    for j in range(W):
        if maze[i][j] == "#":
            visited[i][j] = 0
            queue.append([i, j])

print(bfs(maze, visited, queue, H, W))
### BUGGY CODE ###

from copy import*
from collections import*

d=defaultdict(deque)
s=input()
x=len(s)
t=input()
for k,v in enumerate(s):
    d[v].append(k)
dsub=deepcopy(d)
#print(*d)
if (set(s)>=set(t)):
#    print(d)
    pre=-1
    ans=0
    for i in t:
        if len(d[i])==0:
            d=deepcopy(dsub)
            pre=d[i].popleft()
            ans+=1
        else:
            p=d[i].popleft()
            if p>pre:
                pre=p
            else:
                d=deepcopy(dsub)
                ans+=1
                pre=p
#        print(d.values())
    print(ans*x+pre+1)
else:
    print(-1)
    


### FIXED CODE ###

from bisect import*
s=input()
t=input()
if set(t)<=set(s):
    d={}
    for k,j in enumerate(s*2):
        if j in d:
            d[j].append(k)
        else:
            d[j]=[k]
    #print(d)
    now=-1
    ans=0
    for _,i in enumerate(t):
        nex=d[i][bisect_right(d[i],now)]
        ans+=nex-now

        #print(i,_,now,nex,ans)
        
        if nex>=len(s):
            now=nex-len(s)
        else:
            now=nex
    print(ans)

else:
    print(-1)
### BUGGY CODE ###

def main():
    n, p = map(int, input().split())
    f = {}
    tmp = 0
    while p % 2 == 0:
        tmp += 1
        p //= 2
    f[2] = tmp
    tmp = 3
    while p > 1:
        if p % tmp == 0:
            p //= tmp
            if tmp in f:
                f[tmp] += 1
            else:
                f[tmp] = 1
        else:
            tmp += 2
    f = sorted(f.items(), key=lambda x: x[1], reverse=True)
    answer = 1
    for ff, cnt in f:
        if cnt < n:
            break
        answer *= ff ** (cnt // n)
    print(answer)


if __name__ == '__main__':
    main()



### FIXED CODE ###

from collections import Counter


def main():
    number, product = map(int, input().split())
    prime_factors = []
    while product % 2 == 0:
        prime_factors.append(2)
        product //= 2
    i = 3
    while i * i <= product:
        if product % i == 0:
            product //= i
            prime_factors.append(i)
        else:
            i += 2
    if product != 1:
        prime_factors.append(product)
    prime_factors = Counter(prime_factors)
    answer = 1
    for p, n in prime_factors.items():
        if number <= n:
            answer *= pow(p, n // number)
    print(answer)


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

n=int(input())
ai=[int(x) for x in input().split()]
if (ai.count(0)==1 or ai.count(0)==0)and all([ai.count(i)==0 or ai.count(i)==2 for i in range(1,n)]):
    nd=n//2
    ans=1
    for i in range(nd):
        ans*=2
        ans%=10**9+7
    print(ans)
else:
    print(0)

### FIXED CODE ###

n=int(input())
ai=[int(x) for x in input().split()]
#print(len(set(ai)), -(-n // 2))
if (ai.count(0)==0 or ai.count(0)==1) and len(set(ai))==-(-n//2):
    ans=1
    for i in range(n//2):
        ans*=2
        ans%=10**9+7
    print(ans)
else:
    print(0)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
lr = [list(map(int, input().split())) for _ in range(q)]

for i in range(q):
    left = lr[i][0] - 1
    right = lr[i][1]
    count = s[left:right].count('AC')
    print(count)

### FIXED CODE ###

n, q = map(int, input().split())
s = input()

t = [0] * (n+1)
for i in range(n):
    t[i+1] = t[i] + (1 if s[i:i+2] == 'AC' else 0)

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

def main():
  import sys
  input = sys.stdin.readline
  n=int(input())
  a=tuple(map(int,input().split()))
  ll=len(bin(max(a)))+1
  mod=pow(10,9)+7
  x=[0]*63
  for i in a:
    i=bin(i)
    l=len(i)-1
    for j in range(1,l):
      if i[-j]=='1':
        x[j]+=1
  ans=0
  for i in range(1,ll):
    ans+=pow(2,i-1,mod)*(x[i]%mod)*((n-x[i])%mod)%mod
    ans%=mod
  print(ans)
if __name__=='__main__':
  main()

### FIXED CODE ###

def main():
  import sys
  input = sys.stdin.readline
  import numpy as np
  n=int(input()) 
  a=np.array(list(map(int,input().split())))
  mod=pow(10,9)+7
  ans=0
  
  for i in range(60):
    x=np.count_nonzero(a & 1)
    ans+=pow(2,i,mod)*x*(n-x)
    ans=ans%mod
    a=a>>1
  print(ans)
if __name__=='__main__':
  main()
### BUGGY CODE ###

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

ab = [list(map(int, input().split())) for _ in range(M)]
cd = [list(map(int, input().split())) for _ in range(K)]

lstab = [[] for _ in range(N)]
lstcd = [[] for _ in range(N)]
ans = [[] for _ in range(N)]

for a,b in ab:
    lstab[a-1].append(b-1)
    lstab[b-1].append(a-1)

    
for c,d in cd:
    lstcd[c-1].append(d-1)
    lstcd[d-1].append(c-1)


for i in range(N):
    temp = lstab[i][:]
    visited = []
    visited = [i] + lstab[i]

    while temp:
        x = temp.pop()
        for y in lstab[x]:
            if y in visited:continue
            if not y in lstcd[i]:
                ans[i].append(y)
            temp.append(y)
            visited.append(y)
    
print(*[len(x) for x in ans])


### FIXED CODE ###

import sys
from collections import Counter
input = sys.stdin.readline

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

for _ in range(M):
    a, b = map(int, input().split())
    lstab[a-1].append(b-1)
    lstab[b-1].append(a-1)

visited = [0] * N
cnt = 0

for i in range(N):
    if visited[i] != 0: continue
    temp = [i]
    cnt += 1
    visited[i] = cnt
 
    while temp:
        x = temp.pop()
        for y in lstab[x]:
            if visited[y] != 0:continue
            temp.append(y)
            visited[y] = cnt

numcd = [ 0 ] * N
for _ in range(K):
    c, d = map(int, input().split())
    if visited[c-1] == visited[d-1]:
        numcd[c-1] += 1
        numcd[d-1] += 1    
    
ans = [0] * N
cnt = Counter(visited)

for i in range(N):
    ans[i] = cnt[visited[i]] - 1 - len(lstab[i]) - numcd[i]
 
print(*ans)
### BUGGY CODE ###

q = int(input())
for _ in range(q):
    x = input()
    y = input()
    m = len(x)
    n = len(y)
    c = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
    for i in range(1, m + 1):
        c[i][0] = 0
    for j in range(1, n + 1):
        c[0][j] = 0
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if x[i - 1] == y[j - 1]:
                c[i][j] = c[i - 1][j - 1] + 1
            elif c[i - 1][j] >= c[i][j - 1]:
                c[i][j] = c[i - 1][j]
            else:
                c[i][j] = c[i][j - 1]
    print(c[m][n])


### FIXED CODE ###

def lcs(x, y):
    m = len(x)
    n = len(y)
    c = [0] * (n + 1)
    for i in range(m):
        tmp = x[i]
        c_ = c[:]
        for j in range(n):
            if tmp == y[j]:
                c[j + 1] = c_[j] + 1
            elif c[j + 1] < c[j]:
                c[j + 1] = c[j]
    return c[-1]


q = int(input())
ans = []
for _ in range(q):
    x = input()
    y = input()
    ans.append(lcs(x, y))

print(*ans, sep="\n")
### BUGGY CODE ###



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

N, K = map(int, input().split())
H = list(map(int, input().split()))

dp = [float('inf')] * N
dp[0] = 0
for i in range(N):
    for j in range(i+1, min(i+K+1, N)):
        dp[j] = min(dp[j], abs(H[j]-H[i])+dp[i])
#        print(dp)

print(dp[-1])

### FIXED CODE ###


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

N, K = map(int, input().split())
H = list(map(int, input().split()))

dp = [float('inf')] * N
dp[0] = 0
for i in range(N):
    for j in range(1, K+1):
        if i+j < N:
            dp[i+j] = min(dp[i+j], abs(H[i]-H[i+j])+dp[i])
#        print(dp)

print(dp[-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import numpy as np

L, R = list(map(int, input().split()))

if R-L >= 2019:
    print(0)
else:
    tmp = np.array(range(L, R+1))
    tmp2 = []
    for i in range(len(tmp)):
        for j in range(i+1, len(tmp)):
            tmp2.append((tmp[i] * tmp[j]) % 2019)
    print(min(tmp2))


### FIXED CODE ###

# -*- coding: utf-8 -*-
import numpy as np

L, R = list(map(int, input().split()))

if R-L >= 2019:
    print(0)
else:
    tmp = []
    for i in range(L, R):
        for j in range(i+1, R+1):
            tmp.append((i * j) % 2019)
    print(min(tmp))
### BUGGY CODE ###

MOD = 998244353
n, a, b, k = [int(item) for item in input().split()]

fac = [1] + [0] * n
fac_inv = [1] + [0] * n
for i in range(1, n+1):
    fac[i] = fac[i-1] * (i) % MOD
    fac_inv[i] = fac_inv[i-1] * pow(i, MOD-2, MOD) % MOD

def mod_nCr(n, r):
    if n == 0 and r == 0:
        return 1
    if n < r or n < 0:
        return 0
    tmp = fac_inv[n-r] * fac_inv[r] % MOD
    return tmp * fac[n] % MOD 

if a < b:
    a, b = b, a
max_a_num = k // a + 1
ans = 0
for a_num in range(max_a_num):
    lest = k - (a_num * a)
    if lest % b != 0 or lest < 0:
        continue
    b_num = lest // b
    ans += mod_nCr(n, a_num) * mod_nCr(n, b_num)
    ans %= MOD
print(ans)

### FIXED CODE ###

MOD = 998244353
n, a, b, k = [int(item) for item in input().split()]

fac = [1] + [0] * n
fac_inv = [1] + [0] * n
for i in range(1, n+1):
    fac[i] = fac[i-1] * (i) % MOD
    fac_inv[i] = fac_inv[i-1] * pow(i, MOD-2, MOD) % MOD

def mod_nCr(n, r):
    if n == 0 and r == 0:
        return 1
    if n < r or n < 0:
        return 0
    tmp = fac_inv[n-r] * fac_inv[r] % MOD
    return tmp * fac[n] % MOD 

if a < b:
    a, b = b, a
max_a_num = k // a + 1
ans = 0
for a_num in range(max_a_num):
    lest = k - (a_num * a)
    if lest % b != 0 or lest < 0:
        continue
    b_num = lest // b
    ans += mod_nCr(n, a_num) * mod_nCr(n, b_num)
    ans %= MOD
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
n,m = map(int,input().split())
graph = [[] for _ in range(n)]
for i in range(m):
  x,y = map(int,input().split())
  graph[x-1].append(y-1)
dp = [0]*(n)

done = []
def dfs(i):
    if i in done:
        done.pop()
        if dp[i] < len(done):dp[i] = len(done)
        return len(done)
    for j in graph[i]:
        if not(j in done):
            done.append(i)
            dfs(j)
    if dp[i] < len(done):dp[i] = len(done)
    if done:done.pop()
    return len(done)

for i in range(n):  
    dfs(i)
print(max(dp))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
n,m = map(int,input().split())
graph = [[] for _ in range(n)]
for i in range(m):
  x,y = map(int,input().split())
  graph[x-1].append(y-1)
dp = [-1]*(n)
 
def dfs(i):
    if dp[i] != -1:
        return dp[i]
    else:
        res = 0
        for j in graph[i]:
            res = max(res,dfs(j)+1)
        dp[i] = res
        return dp[i]
 
for i in range(n):  
    dfs(i)
print(max(dp))
### BUGGY CODE ###

import fractions
from functools import reduce
import sys
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

lcm_A = lcm_list(A)
B = [None]*N
for i in range(N):
    B[i] = lcm_A//A[i]

print(int(sum(B)%(10**9+7)))

### FIXED CODE ###

import fractions
import functools
import sys

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return functools.reduce(lcm_base, numbers, 1)
"""
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
"""
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

lcm_A = functools.reduce(lcm_base, A, 1)
B = [None]*N
B = [lcm_A//a for a in A]
#B[i] = lcm_A//A[i]

print(sum(B)%(10**9+7))
### BUGGY CODE ###

n=int(input())
arr=list(map(int,input().split()))
c=1
for i in arr:
    c=c*i
if(c>10**18):
    print(-1)
else:
    print(c)

### FIXED CODE ###

n=int(input())
arr=list(map(int,input().split()))
c=1
arr.sort()
d=0
for i in arr:
    c=c*i
    if(c>10**18):
        d=1
        print(-1)
        break
if(d==0):
    print(c)
### BUGGY CODE ###

import bisect

N = int(input())
arr = list(map(int,input().split()))
arr = sorted(arr)
cnt = 0
for i in range(N-1):
  for j in range(N-i-1):
    a = arr[i]
    b = arr[i+j+1]
    if (i+j+2) < N:
      k = i+j+2
      upper = bisect.bisect_left(arr[k:], (a+b))
      cnt += upper

print(cnt)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a = sorted(a)
def trian(a):
    n=len(a)
    res = 0
    # 最小辺x
    for x in range(n):
        z=x+2
        # 真ん中の辺y
        for y in range(x+1,n):
            # 最大の辺z
            # nより小さく、二辺の和よりも小さい
            while(z<n and a[x]+a[y]>a[z]):
                z+=1
            # y+1から毎回数えるのではなく、yが増えれば、zも増えるのを利用し、前回の値を保存しておく
            res += z-y-1
    return res
print(trian(a))
### BUGGY CODE ###

I = lambda: map(int, input().split())
n, k = I()
a = []
for _ in range(n):
    t, d = I()
    a += [d, t],
a.sort(key = lambda a: a[0], reverse = True)
b = 0
c = [0]*(n+1)
e = 0
s = []
for i in a[:k]:
    b += i[0]
    if c[i[1]] == 0: e += 1
    c[i[1]] += 1
    s += i,
f = b+e**2
for i in range(k, n):
    g = a[i]
    if c[g[1]] > 0: continue
    for j in range(k):
        h = s[::-1][j]
        if c[h[1]] > 1:
            b += g[0]-h[0]
            c[g[1]] += 1
            c[h[1]] -= 1
            s.pop(j)
            s += g,
            e += 1
            f = max(f, b+e**2)
            break
print(f)

### FIXED CODE ###

mi = lambda: map(int, input().split())
n, k = mi()
sushis = [list(mi()) for _ in range(n)]
types = set()
sushis.sort(key = lambda x: x[1], reverse = True)
bp = tp = sp = 0
exts = []
for t, d in sushis[:k]:
    bp += d
    if t in types:
        exts += d,
    else:
        types.add(t)
        tp += 1
sp = bp+tp**2
for t, d in sushis[k:]:
    if not exts: break
    if t not in types:
        types.add(t)
        bp += d-exts.pop()
        tp += 1
        sp = max(sp, bp+tp**2)
print(sp)
### BUGGY CODE ###

import sys
from collections import defaultdict

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

MOD = 10**9 + 7
P = 2 ** 127 - 1

N = int(readline())
m = map(int, read().split())
A, B = zip(*zip(m, m))

pow2 = [1] * (N + 10)
for n in range(1, N + 10):
    pow2[n] = pow2[n - 1] * 2 % MOD

def inv_mod(a):
    b = P
    u, v = 1, 0
    while a:
        q, r = divmod(b, a)
        a, b = r, a
        u, v = v - q * u, u
    if b < 0:
        v = -v
    if v < 0:
        v += P
    return v

pair_key = {0:-1, -1:0}

def to_key(a, b):
    if a == 0:
        return -1
    if b == 0:
        return 0
    x = inv_mod(a) * b % P
    y = P - (inv_mod(b) * a % P)
    pair_key[x] = y
    return x

  
counter = defaultdict(int)
origin = 0
for a, b in zip(A, B):
    if a == b == 0:
        origin += 1
        continue
    key = to_key(a, b)
    counter[key] += 1

answer = origin
k = 1
for key, cnt in counter.items():
    key1 = pair_key[key]
    if key1 not in counter:
        k *= pow2[cnt]
    elif key < key1:
        x, y = cnt, counter[key1]
        k *= pow2[x] + pow2[y] - 1
    k %= MOD
answer += k - 1
answer %= MOD
print(answer)


### FIXED CODE ###

import sys
from collections import defaultdict
from math import gcd

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

MOD = 10**9 + 7

N = int(readline())
m = map(int, read().split())
A, B = zip(*zip(m, m))

pow2 = [1] * (N + 10)
for n in range(1, N + 10):
    pow2[n] = pow2[n - 1] * 2 % MOD

def to_standard_form(a, b):
    if a == 0:
        return (0, 1)
    g = gcd(a, b)
    a //= g
    b //= g
    if a < 0:
        return (-a, -b)
    return (a, b)

counter0 = defaultdict(int)
counter1 = defaultdict(int)
origin = 0
for a, b in zip(A, B):
    if a == b == 0:
        origin += 1
        continue
    a, b = to_standard_form(a, b)
    if b <= 0:
        counter0[(a, b)] += 1
    else:
        counter1[(b, -a)] += 1
        counter0[(b, -a)] += 0

answer = origin
k = 1
for key, cnt0 in counter0.items():
    cnt1 = counter1[key]
    x = pow2[cnt0] + pow2[cnt1]
    k = k * (x - 1) % MOD

answer += k - 1
answer %= MOD
print(answer)
### BUGGY CODE ###

from sys import stdin
input = stdin.readline
I = lambda :list(map(int,input().split()))

n,=I()
l = sorted(I())
g=[0]*(10**6+1)
an=0
for i in range(n):
  x=l[i];f=1
  for j in range(1,int(x**0.5)+1):
    if x%j==0:
      if g[j] or g[x//j]:
        f=0;break
  g[x]=1
  if f and (i!=n-1 and l[i+1]!=l[i]):
    an+=1
  elif f and i==n-1:
    an+=1
print(an)

### FIXED CODE ###

n,a=int(input()),sorted(list(map(int,input().split())))
m,s=a[-1],[0]*(a[-1]+1)
for i in a:
  s[i]+=1
for i in set(a):
	if s[i]:
		for j in range(i*2,m+1,i):s[j]=0
print(s.count(1))