Problem:
 Score: 500 points    Problem Statement  We have caught N sardines. The deliciousness and fragrantness of the i -th sardine is A_i and B_i , respectively.  We will choose one or more of these sardines and put them into a cooler. However, two sardines on bad terms cannot be chosen at the same time.  The i -th and j -th sardines (i \neq j) are on bad terms if and only if A_i \cdot A_j + B_i \cdot B_j = 0 .  In how many ways can we choose the set of sardines to put into the cooler? Since the count can be enormous, print it modulo 1000000007 .      Constraints   All values in input are integers.  1 \leq N \leq 2 \times 10^5  -10^{18} \leq A_i, B_i \leq 10^{18}         Input  Input is given from Standard Input in the following format:  N  A_1  B_1  :  A_N  B_N       Output  Print the count modulo 1000000007 .        Sample Input 1 3
1 2
-1 1
2 -1      Sample Output 1 5  There are five ways to choose the set of sardines, as follows:   The 1 -st  The 1 -st and 2 -nd  The 2 -nd  The 2 -nd and 3 -rd  The 3 -rd        Sample Input 2 10
3 2
3 2
-1 1
2 -1
-3 -9
-8 12
7 7
8 1
8 2
8 4      Sample Output 2 479

Solution (Python):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))



def f(a,b):
    if a == 0:
        return 0,1
    if b == 0:
        return 1,0
    f = math.gcd(a,b)
    return a//f, b//f

N = I()
A,B = LIR(N,2)

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


dplus = defaultdict(int)
dplus2 = defaultdict(int)
dminus = defaultdict(int)
dminus2 = defaultdict(int)
dzeros = defaultdict(int)

zero = 0
both_zero = 0
for i in range(N):
    if A[i] == 0 and B[i] == 0:
        both_zero += 1
    elif A[i] == 0 or B[i] == 0:
        a,b = f(abs(A[i]),abs(B[i]))
        dzeros[(a,b)] += 1
    else:
        if A[i]*B[i] > 0:
            a,b = f(abs(A[i]),abs(B[i]))
            dplus[(a,b)] += 1
            dplus2[(a,b)] += 1
        else:
            a,b = f(abs(A[i]),abs(B[i]))
            dminus[(b,a)] += 1
            dminus2[(b,a)] += 1

ans = 1
count = 0

for k in dplus.keys():
    if dminus[k]:
        temp = beki[dplus[k]] + beki[dminus[k]] - 1
        ans *= temp
        ans %= mod
    else:
        count += dplus[k]

for k in dminus2.keys():
    if dplus2[k]:
        continue
    else:
        count += dminus2[k]

temp = beki[dzeros[(0,1)]] + beki[dzeros[(1,0)]] -1
ans *= temp
ans %= mod

ans *= beki[count]
ans -= 1
ans += both_zero
ans %= mod
print(ans)

Solution (Python):
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res

def gcd(x, y):
    if x < y:
        x = x ^ y
        y = x ^ y
        x = x ^ y
    div = x % y
    while div != 0:
        x = y
        y = div
        div = x % y
    return y


N=II()
MP1={}
A0 = 0
B0 = 0
AB0 = 0
RES=1
for i in range(N):
    A, B = LI()
    if A*B != 0:
        G = gcd(abs(A),abs(B))
        A //= G
        B //= G
        v = (abs(A), abs(B), A*B > 0)
        if not v in MP1:
            MP1[v] = 1
        else:
            MP1[v] += 1

    if A == 0 and B != 0: A0 += 1
    if A != 0 and B == 0: B0 += 1
    if A == 0 and B == 0: AB0 += 1



VIS = set()
for (vv, n) in MP1.items():
    (A, B, isPos) = vv
    v = (B, A, not isPos)
    if not v in VIS and not vv in VIS:
        VIS.add(v)
        VIS.add(vv)
        if v in MP1:
            m = MP1[v]
            RES = (RES*POW(2, n))%DVSR + (RES*POW(2, m))%DVSR - RES
            RES %= DVSR
        else:
            RES *= POW(2, n)
            RES %= DVSR

if A0 and B0:
    RES = (RES*POW(2, A0))%DVSR + (RES*POW(2, B0))%DVSR - RES
elif A0:
    RES = RES*POW(2, A0)%DVSR
elif B0:
    RES = RES*POW(2, B0)%DVSR


print((RES+AB0-1)%DVSR)

Solution (Python):
import math
MOD = 1000000007

def solve(N, ABs):
    groups = {}
    zero_count = 0
    for a, b in ABs:
        if a == 0 and b == 0:
            zero_count += 1
            continue
        if a == 0:
            k = (0, 1)
        elif b == 0:
            k = (1, 0)
        else:
            g = math.gcd(abs(a), abs(b))
            a //= g
            b //= g
            if a * b < 0:
                k = (abs(a), -abs(b))
            else:
                k = (abs(a), abs(b))
        groups.setdefault(k, 0)
        groups[k] += 1

    visited = set()
    possibles = []
    for k, v in groups.items():
        if k in visited:
            continue
        p = 0
        p += pow(2, v, MOD)
        if k[1] == 0:
            m = (0, 1)
        elif k[0] == 0:
            m = (1, 0)
        else:
            if k[1] < 0:
                m = (-k[1], k[0])
            else:
                m = (k[1], -k[0])


        if m in groups.keys() and m not in visited:
            p += pow(2, groups[m], MOD)
            visited.add(m)
            p -= 1
        visited.add(k)
        possibles.append(p % MOD)

    ans = 1
    for p in possibles:
        ans *= p
        ans %= MOD

    if zero_count:
        ans += zero_count
        ans %= MOD
    return (ans - 1) % MOD


def slow_solve(N, ABs):
    import itertools
    ans = 0
    for k in range(1, 2**N):
        b = ("{:0" + str(N) + "b}").format(k)
        taken = []
        for i, c in enumerate(b):
            if c == "1":
                taken.append(ABs[i])

        if len(taken) == 1:
            ans += 1
        elif all(comb[0][0] * comb[1][0] + comb[0][1] * comb[1][1] != 0
                 for comb in itertools.combinations(taken, 2)):
            ans += 1
    return ans % MOD



if __name__ == "__main__":
    N = int(input())
    ABs = [tuple(map(int, input().split(" "))) for _ in range(N)]
    print(solve(N, ABs))

Solution (Python):
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]

def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]

def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().rstrip().split()
def LST2(N): return [sys.stdin.readline().rstrip().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)

MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

from fractions import Fraction

N = I()
cnt = {}
pair = {}
bothzero = 0
for i in range(N):
    A,B = MI()
    if A==0 and B==0:
        bothzero += 1
    elif B==0:
        pair[0]=pair.get(0,0)+1
    elif A == 0:
        cnt[0]=cnt.get(0,0)+1
    elif A/B>0:
        frac = Fraction(A,B).as_integer_ratio()
        
        cnt[frac]=cnt.get(frac,0)+1
    else:
        frac = Fraction(-B,A).as_integer_ratio()
        pair[frac]=pair.get(frac,0)+1
    
res = N-bothzero
ans = 1
for v in cnt:
    if pair.get(v,0)==0:
        continue
    res -= (cnt[v]+pair[v])
    ans = ans*((pow(2,cnt[v],MOD)+pow(2,pair[v],MOD)-1)%MOD)
    ans = ans%MOD
ans = (ans*pow(2,res,MOD)-1)%MOD
ans = (ans+bothzero)%MOD
print(ans)

Solution (Python):

import sys
from math import gcd

N, *AB = map(int, sys.stdin.read().split())

dict_F = {}
count_0 = 0

def insert(A,B,s): 
  if (A,B) not in dict_F.keys():
    dict_F[(A,B)] = [0,0]
  dict_F[(A,B)][s] += 1

def make_power2(N):
  result = 1
  list_result = [1]
  for _ in range(N):
    result = (2*result)%mod
    list_result.append(result)
  return list_result

for i in range(N):
  A,B = AB[2*i], AB[2*i+1]
  if A==0 and B==0:
    count_0 += 1
    continue
  g = gcd(A,B)
  A //= g
  B //= g
  if A>=0 and B>0:
    insert(A,B,0)
  elif A>0 and B<=0:
    insert(-B,A,1)
  elif A<=0 and B<0:
    insert(-A,-B,0)
  elif A<0 and B>=0:
    insert(B,-A,1)

mod = 1000000007
power2 = make_power2(N)
answer = 1

for A,B in dict_F.values():
  answer = (answer*(power2[A]+power2[B]-1))%mod
answer = (answer+count_0-1)%mod

print(answer)

Solution (Python):
import math
MOD = 1000000007
N = int(input())
d_p = dict()
d_m = dict()
zz = 0
for n in range(N):
    a,b = map(int,input().split())

    if a==0 and b==0:
        zz += 1
        continue
    if a==0:
        n_sign = 0
        a=0
        b=0
    elif b==0:
        n_sign = 1
        a=0
        b=0  


    else:    
        n_sign = ((a<0) + (b<0))%2
        a = abs(a)
        b = abs(b)
        gcd = math.gcd(a,b)
        a//=gcd
        b//=gcd
        

    

    if n_sign==1:
        s =str(b)+'/'+str(a)
        d_m[s] = d_m.get(s,0) + 1
    elif n_sign==0:
        s =str(a)+'/'+str(b)
        d_p[s] = d_p.get(s,0) + 1      
    


ans = 1
for k,v in d_m.items():
    if k in d_p:
        ans *= (2**v + 2**d_p[k] - 1)
        
        d_p.pop(k)
    else:
        ans *= 2**v
    ans %= MOD

for k,v in d_p.items():
    ans *= 2**v
    ans %= MOD
ans -= 1
ans += zz
ans %= MOD
print (ans)

Solution (Python):
import sys
sys.setrecursionlimit(100000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15
dy = (-1,0,1,0)
dx = (0,1,0,-1)
from math import gcd

def main():
    N = int(input())
    minus_iwashi = {}
    iwashi = {}
    a0 = 0
    b0 = 0
    a0b0 = 0
    
    for _ in range(N):
        a,b = map(int,input().split())
        if a < 0 and b > 0:
            a = -a
            b = -b
        elif a < 0 and b < 0:
            a = -a
            b = -b
        if a == 0 and b == 0:
            a0b0 += 1
            continue
        if a == 0 and b != 0:
            a0 += 1
            continue
        if b == 0 and a != 0:
            b0 += 1
            continue
        
        if b < 0:
            a,b = -b,a
            
            x = gcd(a,b)
            a //= x
            b //= x
            if (a,b) in minus_iwashi:
                minus_iwashi[(a,b)] += 1
            else:
                minus_iwashi[(a,b)] = 1
        elif b > 0:
            x = gcd(a,b)
            a //= x
            b //= x
            if (a,b) in iwashi:
                iwashi[(a,b)] += 1
            else:
                iwashi[(a,b)] = 1
    
    power = [1]
    for _ in range(N):
        power.append(power[-1]*2%MOD)
    '''
    print(power)
    print(iwashi)
    print(minus_iwashi)
    print(a0,b0)
    '''
    
    if a0 > 0 and b0 > 0:
        ans = (power[a0] + power[b0] - 1)%MOD
    elif a0 > 0:
        ans = power[a0]
    elif b0 > 0:
        ans = power[b0]
    else:
        ans = 1

    for k,v in iwashi.items():
        if k in minus_iwashi:
            ans *= (power[v] + power[minus_iwashi[k]] - 1)%MOD
            ans %= MOD
        else:
            ans *= power[v]
            ans %= MOD
    
    for k,v in minus_iwashi.items():
        if k in iwashi:
            continue
        else:
            ans *= power[v]
            ans %= MOD
    ans += a0b0
    print((ans - 1)%MOD)
if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict
from math import gcd

N = int(input())
MOD = 1000000007
d = defaultdict(int)
num_00 = 0
pow2 = [1]
for i in range(N):
  pow2.append((pow2[-1] * 2) % MOD)

def to_idx(a, b):
  if a == 0 and b != 0:
    return ((0, -1), (0, 1))
  elif a != 0 and b == 0:
    return ((-1, 0), (1, 0))
  else:
    return tuple(sorted(((a, b), (-a, -b))))

ans = 0
for i in range(N):
  a, b = map(int, input().split())
  if a*b == 0 and a != b:
    d[to_idx(a, b)] += 1
  elif a == b == 0:
    num_00 += 1
  else:
    g = gcd(a, b)
    a //= g; b //= g
    d[to_idx(a, b)] += 1

memo = []
key_set = set(d.keys())
while key_set:
  k = key_set.pop()
  v1, v2 = k
  a, b = v1
  idx = to_idx(-b, a)
  memo.append((pow2[d[k]] + pow2[d[idx]] - 1) % MOD)
  key_set.discard(idx)

ans = 1
for m in memo:
  ans *= m
  ans %= MOD

print((ans - 1 + num_00) % MOD)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import Counter
from fractions import Fraction
from math import gcd

N=int(input())
mod=10**9+7

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

def main():
    C=Counter()
    PLUS=0
    for a,b in S:
        if a==0 and b==0:
            PLUS+=1
        elif a==0:
            C[(0,1)]+=1
        elif b!=0 and a>0:
            C[(a//gcd(a,b),b//gcd(a,b))]+=1
        elif b!=0 and a<0:
            C[(-a//gcd(a,b),-b//gcd(a,b))]+=1
            
        else:
            C[float("inf")]+=1
        
    ANS=1

    

    for x in list(C.keys()):
        if x!=float("inf") and x!=(0,1):

            a,b=x

            if b>0:
                ANS=ANS*(pow(2,C[x],mod)+pow(2,C[(b,-a)],mod)-1)%mod
                C[(b,-a)]=0
            else:
                ANS=ANS*(pow(2,C[x],mod)+pow(2,C[(-b,a)],mod)-1)%mod
                C[(-b,a)]=0
                
            C[x]=0

            
        else:
            ANS=ANS*(pow(2,C[float("inf")],mod)+pow(2,C[(0,1)],mod)-1)%mod

            C[float("inf")]=0
            C[(0,1)]=0

    print((ANS-1+PLUS)%mod)

main()

Solution (Python):

from math import gcd

N = int(input())

dict_F = {}
count_0 = 0

def insert(A,B,s): 
  if (A,B) not in dict_F.keys():
    dict_F[(A,B)] = [0,0]
  dict_F[(A,B)][s] += 1

def make_power2(N):
  result = 1
  list_result = [1]
  for _ in range(N):
    result = (2*result)%mod
    list_result.append(result)
  return list_result

for i in range(N):
  A,B = map(int, input().split())
  if A==0 and B==0:
    count_0 += 1
    continue
  g = gcd(A,B)
  A //= g
  B //= g
  if A>=0 and B>0:
    insert(A,B,0)
  elif A>0 and B<=0:
    insert(-B,A,1)
  elif A<=0 and B<0:
    insert(-A,-B,0)
  elif A<0 and B>=0:
    insert(B,-A,1)

mod = 1000000007
power2 = make_power2(N)
answer = 1

for A,B in dict_F.values():
  answer = (answer*(power2[A]+power2[B]-1))%mod
answer = (answer+count_0-1)%mod

print(answer)

Solution (Python):
from collections import Counter
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

def solve():
    MOD = 10**9 + 7

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

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

    cntPos = Counter()
    cntNeg = Counter()
    num00 = 0
    for A, B in ABs:
        if A == B == 0:
            num00 += 1
            continue
        if A == 0:
            cntNeg[(0, 1)] += 1
        elif B == 0:
            cntPos[(0, 1)] += 1
        else:
            isPN = A*B < 0
            A, B = abs(A), abs(B)
            g = gcd(A, B)
            A, B = A//g, B//g
            if isPN:
                cntNeg[(B, A)] += 1
            else:
                cntPos[(A, B)] += 1

    numPoss = []
    numNegs = []

    numIso = 0
    for key in set(cntPos.keys()) | set(cntNeg.keys()):
        if cntPos[key] > 0 and cntNeg[key] > 0:
            numPoss.append(cntPos[key])
            numNegs.append(cntNeg[key])
        else:
            numIso += cntPos[key] + cntNeg[key]

    M = len(numPoss)
    numAlls = [0] * M
    numOKs = [0] * M
    numNGs = [0] * M
    for i in range(M):
        numPos = numPoss[i]
        numNeg = numNegs[i]
        numAll = pow(2, numPos+numNeg, MOD)
        numOK = pow(2, numPos, MOD) + pow(2, numNeg, MOD) - 1
        numNG = numAll - numOK
        numAlls[i] = numAll
        numOKs[i] = numOK
        numNGs[i] = numNG

    acc = pow(2, numIso, MOD)
    accNumAlls = [acc]
    for i in reversed(range(M)):
        acc *= numAlls[i]
        acc %= MOD
        accNumAlls.append(acc)
    accNumAlls.reverse()

    N -= num00
    ans = pow(2, N, MOD) - 1
    accOK = 1
    for i in range(M):
        num = accOK * numNGs[i] * accNumAlls[i+1] % MOD
        ans -= num
        ans %= MOD
        accOK *= numOKs[i]

    print(ans + num00)


solve()

Solution (Python):
def main():
    from math import gcd
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*n]
    adb = dict()
    ans = 0
    mod = 10**9+7
    for a, b in ab:
        if a == b == 0:
            ans += 1
            continue
        if b != 0:
            g = gcd(a, b)
            a = a//g
            b = b//g
            if b < 0:
                a *= -1
                b *= -1
            if a == 0:
                b = 1
            adb[(a, b)] = adb.get((a, b), 0)+1
        else:
            adb[(1, 0)] = adb.get((1, 0), 0)+1
    ans2 = 1
    for i, j in adb.items():
        if i[0] <= 0:
            k = (i[1], -i[0])
        else:
            k = (-i[1], i[0])
        if k not in adb:
            ans2 = ans2*pow(2, j, mod) % mod
        else:
            if i[0] > 0:
                ans2 = ans2*(pow(2, j, mod)+pow(2, adb[k], mod)-1) % mod
    ans2 = (ans2-1) % mod
    print((ans+ans2) % mod)


main()

Solution (Python):
from collections import Counter
import sys
input = sys.stdin.buffer.readline

N = int(input())

def gcd(n, m):
    if m == 0:
        return n
    return gcd(m, n % m)

def make(a, b):
    if a == b == 0:
        return (0, 0, 0)
    if a == 0:
        return (0, 1, 0)
    if b == 0:
        return (1, 0, 0)

    s = 1 if a * b > 0 else -1
    a, b = abs(a), abs(b)

    g = gcd(a, b)
    a //= g
    b //= g

    return (a, b, s)

ABS = Counter([make(*map(int, input().split())) for _ in range(N)])

ans = 1
MOD = 10**9 + 7

for a, b, s in list(ABS.keys()):
    if a == b == 0:
        continue
    p = ABS[(a, b, s)]
    n = ABS[(b, a, -s)]

    ABS[(a, b, s)] = 0
    ABS[(b, a, -s)] = 0

    cnt = pow(2, p, MOD) + pow(2, n, MOD) - 1
    ans = (ans * cnt) % MOD

ans += ABS[(0, 0, 0)]

print((ans - 1) % MOD)

Solution (Python):

import sys
from math import gcd

N, *AB = map(int, sys.stdin.buffer.read().split())

dict_F = {}
count_0 = 0

def insert(A,B,s): 
  if (A,B) not in dict_F.keys():
    dict_F[(A,B)] = [0,0]
  dict_F[(A,B)][s] += 1

def make_power2(N):
  result = 1
  list_result = [1]
  for _ in range(N):
    result = (2*result)%mod
    list_result.append(result)
  return list_result

for i in range(N):
  A,B = AB[2*i], AB[2*i+1]
  if A==0 and B==0:
    count_0 += 1
    continue
  g = gcd(A,B)
  A //= g
  B //= g
  if A>=0 and B>0:
    insert(A,B,0)
  elif A>0 and B<=0:
    insert(-B,A,1)
  elif A<=0 and B<0:
    insert(-A,-B,0)
  elif A<0 and B>=0:
    insert(B,-A,1)

mod = 1000000007
power2 = make_power2(N)
answer = 1

for A,B in dict_F.values():
  answer = (answer*(power2[A]+power2[B]-1))%mod
answer = (answer+count_0-1)%mod

print(answer)

Solution (Python):
import sys; input = sys.stdin.buffer.readline
from collections import defaultdict
from fractions import gcd
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))


def main():
	N = int(input())
	AB = []
	D = defaultdict(int)
	DJ = defaultdict(int)
	d0x = 0
	dx0 = 0
	d00 = 0
	for i in range(N):
		A, B = getlist()
		if A == 0 and B == 0:
			d00 += 1
		elif A == 0:
			dx0 += 1
		elif B == 0:
			d0x += 1
		else:
			GCD = gcd(A, B)
			a = int(A // GCD)
			b = int(B // GCD)
			if a < 0:
				a = -a
				b = -b
			AB.append([a, b])
			D[a * (10 ** 19) + b] += 1
			DJ[a * (10 ** 19) + b] = 1

	ans = 1

	for a, b in AB:
		a2 = b; b2 = -a
		if a2 < 0:
			a2 = -a2; b2 = -b2
		if DJ[a * (10 ** 19) + b] >= 0 and DJ[a2 * (10 ** 19) + b2] >= 0:
			DJ[a * (10 ** 19) + b] = -1
			DJ[a2 * (10 ** 19) + b2] = -1
			X = D[a * (10 ** 19) + b]
			Y = D[a2 * (10 ** 19) + b2]
			ans *= pow(2, X, con) + pow(2, Y, con) - 1
			ans %= con

	ans *= (pow(2, d0x, con) + pow(2, dx0, con)) - 1
	ans += d00
	ans %= con

	if ans == 0:
		print(10 ** 9  + 6)
	else:
		print(ans - 1)

if __name__ == '__main__':
	main()

Solution (Python):
import math
MOD = 1000000007
N = int(input())
d_p = dict()
d_m = dict()
zz = 0
for n in range(N):
    a,b = map(int,input().split())

    if a==0 and b==0:
        zz += 1
        continue
    if a==0:
        n_sign = 1
        a=0
        b=0
    elif b==0:
        n_sign = 0
        a=0
        b=0  


    else:    
        n_sign = ((a<0) + (b<0))%2
        a = abs(a)
        b = abs(b)
        gcd = math.gcd(a,b)
        a//=gcd
        b//=gcd
        

    

    if n_sign==1:
        s =str(b)+'/'+str(a)
        d_m[s] = d_m.get(s,0) + 1
    elif n_sign==0:
        s =str(a)+'/'+str(b)
        d_p[s] = d_p.get(s,0) + 1      
    


ans = 1
for k,v in d_m.items():
    if k in d_p:
        ans *= (2**v + 2**d_p[k] - 1)
        
        d_p.pop(k)
    else:
        ans *= 2**v
    ans %= MOD

for k,v in d_p.items():
    ans *= 2**v
    ans %= MOD
ans -= 1
ans += zz
ans %= MOD
print (ans)

Solution (Python):
def gcd(a,b):
  while b:a,b=b,a%b
  return a
def xy(x,y):
  x,y=abs(x),abs(y)
  g=gcd(x,y)
  x//=g
  y//=g
  return (10**20)*x+y
from collections import defaultdict
mod=10**9+7
n=int(input())
aabb=[list(map(int,input().split()))for _ in range(n)]
ab=[]
ans=0
for i in aabb:
  if i!=[0,0]:ab.append(i)
  else:
    n-=1
    ans+=1
az=bz=0
d=defaultdict(int)
dd=defaultdict(int)
for i in ab:
  if 0 in i:
    if i[0]==0:az+=1
    else:bz+=1
  else:
    a,b=i
    if a*b>0:d[xy(a,b)]+=1
    else:dd[xy(a,b)]+=1
t=[]
tt=1
for i in dd:
  b,a=divmod(i,10**20)
  p,m=d[xy(a,b)],dd[i]
  if p*m:
    n-=p+m
    tt*=(pow(2,p,mod)+pow(2,m,mod)-1)
    tt%=mod
if az*bz:
  n-=az+bz
  tt*=(pow(2,az,mod)+pow(2,bz,mod)-1)
  tt%=mod
ans+=(tt*pow(2,n,mod)-1)%mod
print(ans%mod)

Solution (Python):
import sys
from collections import defaultdict
from queue import deque
readline = sys.stdin.buffer.readline



def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def egcd(a: int, b: int):
    """
    A solution of ax+by=gcd(a,b). Returns
    (gcd(a,b), (x, y)).
    """
    if a == 0:
        return b, 0, 1
    else:
        g, x, y = egcd(b % a, a)
        return g, y - (b // a) * x, x


def modinv(a: int, mod: int = 10**9 + 7):
    """
    Returns a^{-1} modulo m.
    """
    g, x, y = egcd(a, mod)
    if g > 1:
        raise Exception('{}^(-1) mod {} does not exist.'.format(a, mod))
    else:
        return x % mod


def modpow(a: int, n: int, mod: int = 10**9 + 7):
    """
    Returns a^n mod m. (-inf < n < inf)
    """
    if a in [-1, 0, 1]:
        if a == -1:
            return 1 if n & 1 == 0 else mod - 1
        else:
            return a

    x, k = (a % mod, n) if n >= 0 else (modinv(a, mod), -n)

    ret = 1
    while k > 0:
        if k & 1 == 1:
            ret = ret * x % mod
        x = (x**2) % mod
        k = k >> 1

    return ret


def main():
    N = gete(int)

    d = dict()

    for _ in range(N):
        a, b = geta(int)
        if a == b == 0:
            if (0, 0) in d:
                d[(0, 0)] += 1
            else:
                d[(0, 0)] = 1
            continue

        if a != 0 and b != 0:
            g, _, _ = egcd(a, b)
            ai, bi = a // g, b // g
            if ai < 0:
                ai *= -1
                bi *= -1

            aj, bj = bi, -ai
            if aj < 0:
                aj *= -1
                bj *= -1
        elif a == 0:
            ai, bi = 0, 1
            aj, bj = 1, 0
        elif b == 0:
            ai, bi = 1, 0
            aj, bj = 0, 1

        if (ai, bi) in d:
            d[(ai, bi)][0] += 1
        elif (aj, bj) in d:
            d[(aj, bj)][1] += 1
        else:
            d[(ai, bi)] = [1, 0]

    mod = 1000000007
    ans = 1
    for k in d:
        if k != (0, 0):
            n = modpow(2, d[k][0], mod)
            m = modpow(2, d[k][1], mod)

            ans = ans * (n + m - 1) % mod
    if (0, 0) in d:
        ans = (ans + d[(0, 0)]) % mod

    print((ans - 1) % mod)


if __name__ == "__main__":
    main()

Solution (Python):
from math import gcd
import sys
input = sys.stdin.readline

mod = 10**9 + 7
N = int(input())
cnt = {}
zz = 0
az = 0
bz = 0
for _ in range(N):
    A, B = map(int, input().split())
    if A == B == 0:
        zz += 1
        continue
    if A == 0:
        az += 1
        continue
    if B == 0:
        bz += 1
        continue
    neg = False
    if A < 0:
        neg ^= True
        A *= -1
    if B < 0:
        neg ^= True
        B *= -1
    g = gcd(A, B)
    sign = -1 if neg else 1
    A //= g
    B //= g
    frac = (-sign * A, B)
    if frac not in cnt:
        cnt[frac] = 0
    cnt[frac] += 1
ans = 1
used = set()
for frac, c in cnt.items():
    if frac in used:
        continue
    A, B = frac
    sign = 1
    if A < 0:
        A *= -1
        sign = -1
    bad = (B * -sign, A)
    if bad in cnt:
        b = cnt[bad]
        ans = ans * (pow(2, c, mod) + pow(2, b, mod) - 1) % mod
        used.add(bad)
    else:
        ans = ans * pow(2, c) % mod
ans = ans * (pow(2, az, mod) + pow(2, bz, mod) - 1) % mod
print((ans + zz - 1) % mod)

Solution (Python):
import os
from collections import Counter

import itertools
import math
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


N = int(sys.stdin.buffer.readline())
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N)]

zero = 0
A = []
B = []
for a, b in AB:
    if a == b == 0:
        zero += 1
    elif a == 0:
        A.append(0)
        B.append(1)
    elif b == 0:
        A.append(1)
        B.append(0)
    else:
        if a < 0:
            a = -a
            b = -b
        g = math.gcd(a, b)
        A.append(a // g)
        B.append(b // g)

ab = [(a, b) for a, b in zip(A, B)]
ba = [(b, a) for a, b in zip(A, B)]

counts = Counter(ba)
ans = 1
nandemo = 0
seen = set()
for (a, b), cnt in Counter(ab).items():
    cc = counts[-a, b] + counts[a, -b]
    if cc == 0:
        nandemo += cnt
    else:
        if not ((a, -b) in seen or (-a, b) in seen):
            seen.add((b, a))
            seen.add((-b, -a))
            ans *= pow(2, cnt, MOD) + pow(2, cc, MOD) - 1
            ans %= MOD

ans *= pow(2, nandemo, MOD)
ans += zero
ans -= 1
ans %= MOD
print(ans)


def test():
    ans = 0
    for choices in itertools.product([True, False], repeat=N):
        iwasi = []
        for i, c in enumerate(choices):
            if c:
                iwasi.append(AB[i])
        ok = True
        for (a, b), (c, d) in itertools.combinations(iwasi, r=2):
            ok &= a * c + b * d != 0
        if ok:
            print(iwasi)
        ans += ok
    print(ans - 1)

Solution (Python):
from collections import defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def rev(a,b):
    if b<0:
        return (-b,a)
    else:
        return (b,-a)

import math
n = inn()
ab = []
h = defaultdict(int)
badpairs = {}
ab0 = a0 = b0 = 0
for i in range(n):
    a,b = inm()
    if a==b==0:
        ab0 += 1
    elif a==0:
        a0 += 1
    elif b==0:
        b0 += 1
    else:
        g = math.gcd(a,b)
        a //= g
        b //= g
        if a<0:
            a = -a
            b = -b
        h[(a,b)] += 1
        ra,rb = rev(a,b)
        if (ra,rb) in h:
            badpairs[(a,b)] = badpairs[(ra,rb)] = 1
ddprint(h)
ddprint(badpairs)

grps = []
g0 = 0
if a0>0 and b0>0:
    grps.append(pow(2,a0,R)+pow(2,b0,R)-1)
else:
    g0 += a0 + b0
ddprint(g0)
ddprint(grps)
done = {}
for a,b in h:
    if (a,b) in badpairs:
        if (a,b) not in done:
            ra,rb = rev(a,b)
            grps.append(pow(2,h[(a,b)],R)+pow(2,h[(ra,rb)],R)-1)
            done[(a,b)] = done[(ra,rb)] = 1
    else:
        g0 = (g0 + h[(a,b)]) % R
ddprint(g0)
prod = pow(2,g0,R)
for x in grps:
    prod = (prod * x)%R
print((ab0+prod-1)%R)

Solution (Python):
import math
from collections import Counter

N = int(input())
A_B = []
mod = 1000000007
for _ in range(N):
    A, B = map(int, input().split())
    if (A == 0) and (B == 0):
        A_B.append((A, B))
    elif A == 0:
        A_B.append((0, -1))
    elif B == 0:
        A_B.append((1, 0))
    else:
        if A < 0:
            A = -A
            B = -B
        C = math.gcd(abs(A), abs(B))
        A_B.append((A // C, B // C))

A_B_C = Counter(A_B)


ans = 1
Done = set([])
Done.add((0, 0))
for key, value in A_B_C.items():
    if key in Done:
        continue
    keya, keyb = key
    a = 0
    if keya == 0 and keyb == 0:
        a = value + 1
        Done.add((0, 0))
    else:
        if keyb < 0:
            keya = -keya
            keyb = -keyb
        if (keyb, -keya) not in A_B_C:
            a = pow(2, value, mod)
        else:
            a = (pow(2, value, mod) - 1) + (pow(2, A_B_C[(keyb, -keya)], mod) - 1) + 1
            Done.add((keyb, -keya))
    ans *= a
    ans %= mod
    Done.add(key)
ans -= 1
ans += A_B_C[(0, 0)]

print(ans % mod)

Solution (Python):

import math
n = int(input())
a = [0] * n;  b = [0] * n;
for i in range(n):
    a[i], b[i] = [int(x) for x in input().split()]
p = 10 ** 9 + 7


dict = {}
for i in range(n):
    d = math.gcd(a[i], b[i])
    if d > 0:
        aa = a[i] // d
        bb = b[i] // d
    else:
        aa = a[i]
        bb = b[i]
    if aa < 0: 
        aa = -aa
        bb = -bb
    if aa == 0 and bb > 0:
        bb = -bb
    
    if (aa, bb) in dict:
        dict[(aa, bb)] += 1
    else:
        dict[(aa, bb)] = 1

bad = []
others = []
zeros = 0

for (aa, bb) in dict:
    if dict[(aa, bb)] == 0: continue
    if aa == 0 and bb == 0:
        zeros += dict[(aa, bb)]
        dict[(aa, bb)] = 0
    elif (bb, -aa) in dict:
        bad.append((dict[(aa, bb)], dict[(bb, -aa)]))
        dict[(bb, -aa)] = 0
    elif (-bb, aa) in dict:
        bad.append((dict[(aa, bb)], dict[(-bb, aa)]))
        dict[(-bb, aa)] = 0
    else:
        others.append(dict[(aa, bb)])
    dict[(aa, bb)] = 0

ans = 1
for (x, y) in bad:
    ans = ans * (pow(2, x, p) + pow(2, y, p) - 1) % p
for z in others:
    ans = ans * pow(2, z, p) % p
ans = (ans - 1) % p
if zeros > 0:
    ans = (ans + zeros) % p
print(ans)