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):
from fractions import Fraction
import sys
def input():
    return sys.stdin.readline().rstrip('\n')

ZERO = Fraction(0, 1)
Z = 1000000007

class Pow:
    def __init__(self, n):
        self.N = n
        self.e = [1] * (n + 1)
        for i in range(n):
            self.e[i + 1] = (self.e[i] * 2) % Z
    def get(self, n):
        if self.N >= n:
            return self.e[n]
        else:
            for i in range(self.N + 1, n + 1):
                self.e += [(self.e[i] * 2) % Z]
            return self.e[n]


def calc(N, G):
    zz = 0
    r = {}
    r_max = 0
    for a, b in G:
        if b == 0:
            if a == 0:
                zz += 1
            else:
                if 0 in r:
                    r[0][1][1] += 1
                else:
                    r[0] = {1: [0, 1]}
                r_max = max(r_max, r[0][1][1])
        else:
            if a == 0:
                if 0 in r:
                    r[0][1][0] += 1
                else:
                    r[0] = {1: [1, 0]}
                r_max = max(r_max, r[0][1][0])
            else:
                f = Fraction(a, b)
                if f > 0:
                    i = f.numerator
                    j = f.denominator
                    if i in r:
                        if j in r[i]:
                            r[i][j][0] += 1
                        else:
                            r[i][j] = [1, 0]
                    else:
                        r[i] = {j: [1, 0]}
                    r_max = max(r_max, r[i][j][0])
                else:
                    i = f.denominator
                    j = -f.numerator
                    if i in r:
                        if j in r[i]:
                            r[i][j][1] += 1
                        else:
                            r[i][j] = [0, 1]
                    else:
                        r[i] = {j: [0, 1]}
                    r_max = max(r_max, r[i][j][1])
    ans = 1
    pow = Pow(r_max)
    for i in r:
        for j in r[i]:
            ans = (ans * (pow.get(r[i][j][0]) + pow.get(r[i][j][1]) - 1)) % Z
    return (ans + zz - 1) % Z

    

N = int(input())
G = [tuple([int(s) for s in input().split()]) for _ in range(N)]
print(calc(N, G))

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

n=int(input())
a= [list(map(int, input().split())) for i in range(n)]
b=defaultdict(int)
c=defaultdict(int)
b0=0
c0=0
mod=1000000007
ans=1
cnt=0
for i,j in a:
    if i!=0 and j!=0:
        x=i
        y=j
        i //= math.gcd(x, y)
        j //= math.gcd(x, y)
        i=abs(i)
        j=abs(j)
        if x*y>0:
            b[(i,j,0)]+=1
            c[(j,i,1)]+=1
        else:
            b[(i,j,1)]+=1
            c[(j,i,0)]+=1

    elif i==0 and j!=0:
        b0+=1
    elif i!=0 and j==0:
        c0+=1
    else:
        cnt+=1
w=[]
if c0!=0 or b0!=0:
    ans*=pow(2,c0+b0)-((pow(2,c0,mod)-1)*(pow(2,b0,mod)-1))

for k,v in b.items():
    if c[k]!=0:
        ans*=(pow(2,c[k]+v,mod)-(pow(2,c[k],mod)-1)*(pow(2,v,mod)-1))
        w.append((pow(2,c[k]+v,mod)-(pow(2,c[k],mod)-1)*(pow(2,v,mod)-1)))
        ans%=mod
    else:
        ans*=pow(2,v,mod)
        ans%=mod

w=collections.Counter(w)
w=list(w.most_common())
for i,j in w:
    for k in range(j//2):
        ans*=pow(i,mod-2,mod)
ans+=cnt-1
print(int(ans%mod))

Solution (Python):
import sys
from collections import Counter
from math import gcd

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
C = Counter()
zero = 0
for i in range(N):
    a, b = MAP()
    if a == b == 0:
        zero += 1
    elif a == 0:
        C[(0, 1, 0)] += 1
    elif b == 0:
        C[(1, 0, 1)] += 1
    else:
        g = gcd(a, b)
        ga, gb = a // g, b // g
        C[((a < 0) ^ (b < 0), abs(ga), abs(gb))] += 1

ans = 1
for k, v in C.items():
    if v == 0:
        continue
    op, a, b = k
    ans *= pow(2, C[(op, a, b)], MOD) + pow(2, C[(1-op, b, a)], MOD) - 1
    ans %= MOD
    if (1-op, b, a) in C:
        C[(1-op, b, a)] = 0
print((zero+ans-1)%MOD)

Solution (Python):

import math 
n=int(input())
d=dict()
for i in range(n):
    a,b=map(int,input().split())
    if a==0 and b==0:
        pass
    elif a==0:
        a,b=0,1
    elif b==0:
        a,b=1,0
    else:
        x=math.gcd(abs(a),abs(b))
        a,b=a//x,b//x
        if a<0:
            a,b=-a,-b
    if (a,b) in d:
        d[(a,b)]+=1
    else:
        d[(a,b)]=1


ans1,ans2=1,0
for i in d:
    if d[i]==0:
        continue
    if i==(0,0):
        ans2=d[i]
        d[i]=0
        continue
    a,b=i
    if (-b,a) in d:
        ans1*=(2**(d[i])+2**(d[(-b,a)])-1)
        d[(-b,a)]=0
        d[i]=0
    elif (b,-a) in d:
        ans1*=(2**(d[i])+2**(d[(b,-a)])-1)
        d[(b,-a)]=0
        d[i]=0
    else:
        ans1*=(2**(d[i]))
        d[i]=0
print((ans1+ans2-1)%(10**9+7))

Solution (Python):
import sys
INF = 1 << 60
MOD = 10**9 + 7 
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from math import gcd
from collections import Counter
from fractions import Fraction

def resolve():
    n = int(input())
    zero = 0
    counter = Counter()
    for _ in range(n):
        x, y = map(int, input().split())
        if x == 0 and y == 0:
            zero += 1
            continue

        g = gcd(x, y)
        x //= g
        y //= g

        if x == 0:
            x, y = 0, 1
        elif x < 0:
            x, y = -x, -y
        counter[x, y] += 1

    C = list(counter.items())
    C.sort(key = lambda p: Fraction(p[0][1], p[0][0]) if p[0][0] != 0 else -float("inf"))

    k = len(C)
    dp = [0] * (k + 1)
    dp[0] = 1
    for i in range(k):
        x, y = C[i][0]
        dp[i + 1] += dp[i]
        dp[i + 1] += (pow(2, counter[x, y], MOD) - 1) * dp[i] * pow(2, -counter[y, -x] % (MOD - 1), MOD)
        dp[i + 1] %= MOD

    res = dp[k]
    res -= 1
    res += zero
    print(res % MOD)
resolve()

Solution (Python):
import sys
import math
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict

MOD = 10**9+7
N = int(input())
dic = defaultdict(int)
zero = 0
for i in range(N):
    a, b = map(int, input().split())
    if b < 0:
        a = -a
        b = -b
    if a == 0 and b == 0:
        zero += 1
        continue
    elif a == 0:
        b = 1
    elif b == 0:
        a = 1
    g = math.gcd(a, b)
    a //= g
    b //= g
    dic[a,b] += 1
done = set()
ans = 1
for a,b in dic:
    k = (a, b)
    if k in done: continue
    c, d = -b, a
    if d <= 0:
        c = -c
        d = -d
    rk = (c, d)
    done.add(k)
    done.add(rk)
    c = pow(2, dic[k], MOD)-1
    if rk in dic:
        c += pow(2, dic[rk], MOD)-1
    c += 1
    ans *= c
    ans %= MOD
print((ans+zero-1)%MOD)

Solution (Python):
import sys
INF = 1 << 60
MOD = 10**9 + 7 
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from math import gcd
from collections import Counter
from functools import cmp_to_key

def cmp(A1, A2):
    x1, y1 = A1[0]
    x2, y2 = A2[0]
    if (x1, y1) == (x2, y2):
        return 0
    return -1 if x2 * y1 < x1 * y2 else 1

def resolve():
    n = int(input())
    zero = 0
    counter = Counter()
    for _ in range(n):
        x, y = map(int, input().split())
        if x == 0 and y == 0:
            zero += 1
            continue

        g = gcd(x, y)
        x //= g
        y //= g

        if y == 0:
            x, y = 1, 0
        elif y < 0:
            x, y = -x, -y
        counter[x, y] += 1

    C = list(counter.items())
    C.sort(cmp_to_key(cmp))

    k = len(C)
    dp = [0] * (k + 1)
    dp[0] = 1
    for i in range(k):
        x, y = C[i][0]
        dp[i + 1] += dp[i]
        dp[i + 1] += (pow(2, counter[x, y], MOD) - 1) * dp[i] * pow(2, -counter[y, -x] % (MOD - 1), MOD)
        dp[i + 1] %= MOD

    res = dp[k]
    res -= 1
    res += zero
    print(res % MOD)
resolve()

Solution (Python):
import math
import bisect
MOD = 1000000007

N = int(input())
ABs =  []

count00 = 0
for i in range(N):
  A, B = map(int, input().split())
  if A == 0:
    if B == 0:
      count00 += 1
    else:
      ABs.append([0, -1])
  elif B == 0:
    ABs.append([1, 0])
  else:
    mygcd = math.gcd(A, B)
    A, B = A//mygcd, B//mygcd
    if A < 0:
      ABs.append([-A, -B])
    else:
      ABs.append([A, B])
  
N2 = N - count00
if N2 == 0:
  print(count00)
  exit()

ABs.sort(key = lambda x:x[1])
Bs = [i[1] for i in ABs]
index0 = bisect.bisect_left(Bs, 0)

if (index0==0) or (index0==N2):
  print((pow(2, N2, MOD) +count00 -1) %MOD)
  exit()

btm = ABs[:index0]
top = ABs[index0:]

lenbtm = index0
lentop = N2 - index0
for i in range(lenbtm):
  btm[i] = [-btm[i][1], btm[i][0]]

btmdict = {}
topdict = {}
for i in btm:
  mykey = str(i[0]) + '-' + str(i[1])
  btmdict[mykey] = 0
  topdict[mykey] = 0
for j in top:
  mykey = str(j[0]) + '-' + str(j[1])
  btmdict[mykey] = 0
  topdict[mykey] = 0

for i in btm:
  mykey = str(i[0]) + '-' + str(i[1])
  btmdict[mykey] += 1
for j in top:
  mykey = str(j[0]) + '-' + str(j[1])
  topdict[mykey] += 1

ans = 1
for i in btmdict:
  btmi = btmdict[i]
  topi = topdict[i]
  if btmi*topi >= 1:
    ans = ans * (pow(2, btmi, MOD) +pow(2, topi, MOD) -1) %MOD
  elif btmi == 0:
    ans = ans * pow(2, topi, MOD) %MOD
  else:
    ans = ans * pow(2, btmi, MOD) %MOD

ans = (ans +count00 -1) %MOD
print(ans)

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


MOD = 1000000007
N = int(input())
both_zeros_cnt = 0
bads = defaultdict(lambda: [0, 0])
for _ in range(N):
    A, B = map(int, input().split())
    if A == 0 and B == 0:
        both_zeros_cnt += 1
        continue
    if B < 0 or (B == 0 and A < 0):
        A, B = -A, -B
    g = gcd(A, B)
    A, B = A // g, B // g
    if A > 0:
        bads[(A, B)][0] += 1
    else:
        bads[(B, -A)][1] += 1


NMAX = 2 * 10 ** 5 + 1
pow2 = [1] * (NMAX + 1)
for i in range(1, NMAX + 1):
    pow2[i] = pow2[i - 1] * 2 % MOD
ans = 1
for k, l in bads.values():
    ans *= pow2[k] + pow2[l] - 1
    ans %= MOD
print((ans + both_zeros_cnt - 1) % MOD)

Solution (Python):
import math
import collections

N = int(input())

count_both = 0
count = collections.defaultdict(lambda: [0]*2)
for _ in range(N):
  a, b  = [int(x) for x in input().split(' ')]
  if a == 0 and b == 0:
    count_both += 1
    continue
  if a == 0:
    count[(1, 0)][0] += 1
    continue
  if b == 0:
    count[(1, 0)][1] += 1
    continue
    
  s = math.copysign(1, a*b)
  a = abs(a)
  b = abs(b)
  g = math.gcd(a, b)
  if s > 0:
    count[(a//g, b//g)][0] += 1
  else:
    count[(b//g, a//g)][1] += 1

ans = 1
for _, p in count.items():
  ans *= (2**p[0] + 2**p[1] - 1)
  ans %= 1000000007

ans += count_both + 1000000007 - 1
ans %= 1000000007


print(ans)

Solution (Python):

import sys
from collections import defaultdict
from math import gcd

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))


MOD = 10 ** 9 + 7
N = ir()
AB = [lr() for _ in range(N)]  
dic = defaultdict(set)
zero = [set() for _ in range(3)]
for i, (a, b) in enumerate(AB, 1):
    g = gcd(a, b)
    
    if a != 0 and b != 0:
        a //= g; b //= g
        if a < 0:
            a *= -1; b *= -1
        dic[(a, b)].add(i)
    elif a == 0:
        if b == 0:
            zero[0].add(i)
        else:
            zero[1].add(i)
    elif b == 0:
        zero[2].add(i)

answer = 1
used = set()
for k, v in dic.items():
    a, b = k
    k2 = (-b, a)
    if -b < 0:
        k2 = (b, -a)
    if k in used:
        continue
    if k2 in dic:
        v2 = dic[k2]
        answer *= (-1 + pow(2, len(v), MOD) + pow(2, len(v2), MOD))
        used.add((k2))
    else:
        answer *= pow(2, len(v), MOD)
    used.add(k)
    answer %= MOD


answer *= -1 + pow(2, len(zero[1]), MOD) + pow(2, len(zero[2]), MOD)
answer += len(zero[0])
answer -= 1  
print(answer % MOD)

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


MOD = 1000000007
N = int(input())
both_zeros_cnt = 0
bads = defaultdict(lambda: [0, 0])
for _ in range(N):
    A, B = map(int, input().split())
    if A == 0 and B == 0:
        both_zeros_cnt += 1
        continue
    if B < 0 or (B == 0 and A < 0):
        A, B = -A, -B
    g = gcd(A, B)
    A, B = A // g, B // g
    if A > 0:
        bads[(A, B)][0] += 1
    else:
        bads[(B, -A)][1] += 1

ans = 1
for k, l in bads.values():
    ans *= (pow(2, k, MOD) - 1) + (pow(2, l, MOD) - 1) + 1
    ans %= MOD
print((ans + both_zeros_cnt - 1) % MOD)

Solution (Python):
n = int(input())
MOD = 1000000007

ans = 1
x_sardines = []
ver_sardines = []
hor_sardines  = []
zero_sardines  = []

for _ in range(n):
  ai, bi = map(int, input().split())
  if ai == 0 and bi != 0:
    ver_sardines.append((ai, bi))
  elif ai != 0 and bi == 0:
    hor_sardines.append((ai, bi))
  elif ai == 0 and bi == 0:
    zero_sardines.append((ai, bi))
  elif bi / ai > 0:
    x_sardines.append((ai, bi, 1))
  elif bi / ai < 0:
    x_sardines.append((- 1 * bi, ai, -1))

x_sardines.sort(key = lambda x: x[1] / x[0])

if len(x_sardines) > 0:
  pai, pbi, ps = x_sardines[0]
  p = 1 if ps == 1 else 0
  n = 1 if ps == -1 else 0
  for i, (ai, bi, s) in enumerate(x_sardines[1:]):
    if pai * bi - pbi * ai != 0:
      ans *= pow(2, p, MOD) + pow(2, n, MOD) - 1
      ans %= MOD
      p = 0
      n = 0
      
    if s == 1:
      p += 1
    elif s == -1:
      n += 1
    pai, pbi, ps = ai, bi, s

  ans *= pow(2, p, MOD) + pow(2, n, MOD) - 1
  ans %= MOD
  
v = len(ver_sardines)
h = len(hor_sardines)
ans *= pow(2, v, MOD) + pow(2, h, MOD) - 1
ans %= MOD

z = len(zero_sardines)
ans += z
ans -= 1
ans %= MOD

print(ans)

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

n = int(input())
ab = [list(map(int, input().split())) for _ in range(n)]
mod = 10 ** 9 + 7
MAX = 2 * 10 ** 5

p = defaultdict(int)
m = defaultdict(int)
ab0 = 0
for a, b in ab:
    if a == 0 and b == 0:
        ab0 += 1

    elif a == 0:
        m[(0, 1)] += 1
        p[(1, 0)]

    elif b == 0:
        p[(1, 0)] += 1

    else:
        g = gcd(a, b)
        a //= g
        b //= g
        sign = a * b
        a = abs(a)
        b = abs(b)
        if sign < 0:
            m[(a, b)] += 1
            p[(b, a)]
        else:
            p[(a, b)] += 1

power = [1]
for _ in range(MAX):
    power.append(power[-1] * 2 % mod)

ans = 1
for (a, b), v in p.items():
    ans *= power[v] + power[m[(b, a)]] - 1
    ans %= mod

ans -= 1
ans += ab0
ans %= mod
print(ans)

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**19
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N = NI()
    AB = [LI() for _ in range(N)]
    d = {}

    ans = 0
    zero = 0
    for i in range(N):
        a,b = AB[i]
        if a == 0:
            if b == 0:
                zero += 1
                continue
            b = 1
            s = 1
        elif b == 0:
            a = 1
            s = -1
        else:
            s = (a*b>0) - (a*b<0)
            a = abs(a); b = abs(b)
            x = math.gcd(a,b)
            a = a // x; b = b // x
        if (a,b,s) in d:
            d[(a,b,s)] += 1
        else:
            d[(a,b,s)] = 1

    ans = 1
    for (a,b,s),data in d.items():
        if data == 0: continue
        if (b, a, -s) in d:
            m = d[(b,a,-s)]
            d[(b, a, -s)] = 0
        else:
            m = 0
        x = pow(2,data,MOD) + pow(2,m,MOD) - 1
        ans = (ans * x) % MOD

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

if __name__ == '__main__':
    main()

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()
    z = 0

    for _ in range(N):
        a, b = geta(int)
        if a == b == 0:
            z += 1
            continue

        if a != 0 and b != 0:
            g, _, _ = egcd(a, b)
            ai, bi = a // g, b // g
            c1 = (ai, bi) if ai > 0 else (-ai, -bi)
            c2 = (bi, -ai) if bi > 0 else (-bi, ai)
        elif a == 0:
            c1 = (0, 1)
            c2 = (1, 0)
        elif b == 0:
            c1 = (1, 0)
            c2 = (0, 1)

        if c1 in d:
            d[c1][0] += 1
        elif c2 in d:
            d[c2][1] += 1
        else:
            d[c1] = [1, 0]

    mod = 1000000007
    ans = 1
    for k in d:
        n = modpow(2, d[k][0], mod)
        m = modpow(2, d[k][1], mod)
        ans = ans * (n + m - 1) % mod

    ans = (ans + z - 1) % mod

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
AB = [[int(_) for _ in input().split()] for i in range(N)]

from math import gcd

def normalize(x, y):
    if x == 0 and y == 0:
        return (0, 0)
    if x == 0:
        return (0, 1)
    if y == 0:
        return (1, 0)
    if x < 0:
        x, y = -x, -y
    d = gcd(x, y)
    return (x // d, y // d)

def rev(x, y):
    x, y = -y, x
    if x < 0:
        x, y = -x, -y
    return x, y

xs = {}
xszero = 0

for a, b in AB:
    if a == 0 and b == 0:
        xszero += 1
        continue
    nab = normalize(a, b)
    rab = rev(*nab)
    if nab in xs:
        xs[nab][0] += 1
    elif rab in xs:
        xs[rab][1] += 1
    else:
        xs[nab] = [1, 0]

M = 1000000007

result = 1
for ab, nm in xs.items():
    k = (pow(2, nm[0], M) + pow(2, nm[1], M) - 1) % M
    result = (result * k) % M

print((result - 1 + xszero) % M)

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

n = int(input())
ab = [list(map(int, input().split())) for _ in range(n)]
mod = 10 ** 9 + 7

p = defaultdict(int)
m = defaultdict(int)
ab0 = 0
for a, b in ab:
    if a == 0 and b == 0:
        ab0 += 1

    elif a == 0:
        m[(0, 1)] += 1
        p[(1, 0)]

    elif b == 0:
        p[(1, 0)] += 1

    else:
        g = gcd(a, b)
        a //= g
        b //= g
        sign = a * b
        a = abs(a)
        b = abs(b)
        if sign < 0:
            m[(a, b)] += 1
            p[(b, a)]
        else:
            p[(a, b)] += 1

ans = 1
for (a, b), v in p.items():
    ans *= pow(2, v, mod) + pow(2, m[(b, a)], mod) - 1
    ans %= mod

ans -= 1
ans += ab0
ans %= mod
print(ans)

Solution (Python):

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,cos,radians,sqrt
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7



def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
n=I()
bekit=[0 for i in range(n+1)]
bekit[0]=1
for i in range(n):
    bekit[i+1]=(bekit[i]*2)%mod

countz=0
countx=0
county=0
nump=[]
numm=[]
for i in range(n):
    a,b=MI()
    if a==0 and b==0:
        countz+=1
    elif a==0:
        if b<0:
            b*=(-1)
        countx+=1
    elif b==0:
        if a<0:
            a*=(-1)
        county+=1
    elif a*b<0:
        
        if b<0:
            a*=(-1)
            b*=(-1)
        g=gcd(abs(a),b)
        a=a//g
        b=b//g
        
        numm.append([a,b])
    else:
        g=gcd(abs(a),abs(b))
        a//=g
        b//=g
        nump.append([abs(a),abs(b)])


nump=list(map(tuple,nump))
numm=list(map(tuple,numm))
u=Counter(nump)
v=Counter(numm)


nums=[]
pairs=[]
for k in u.keys():
    vz=((-1)*k[1],k[0])
    s=u[k]
    t=v[vz]
    
    
    
    if t>0:
        nums.append([s,t])
        pairs.append(s+t)





if countx>0 and county>0:
    cou=countx+county
else:
    cou=0
ans=bekit[n-sum(pairs)-cou-countz]

for j in range(len(nums)):
    q=bekit[nums[j][0]]
    p=bekit[nums[j][1]]
    
    
    ans=(ans*(q+p-1))%mod
if countx>0 and county>0:
    ans=(ans*(bekit[countx]+bekit[county]-1))%mod
ans-=1
if countz>0:
    ans+=countz%mod
print(ans%mod)

Solution (Python):

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,cos,radians,sqrt
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7



def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
n=I()
bekit=[0 for i in range(n+1)]
bekit[0]=1
for i in range(n):
    bekit[i+1]=(bekit[i]*2)%mod

countz=0
countx=0
county=0
nump=[]
numm=[]
for i in range(n):
    a,b=MI()
    if a==0 and b==0:
        countz+=1
    elif a==0:
        if b<0:
            b*=(-1)
        countx+=1
    elif b==0:
        if a<0:
            a*=(-1)
        county+=1
    elif (a>0 and b<0) or (a<0 and b>0):
        
        if b<0:
            a*=(-1)
            b*=(-1)
        g=gcd(abs(a),b)
        a=a//g
        b=b//g
        
        numm.append([a,b])
    else:
        g=gcd(abs(a),abs(b))
        a//=g
        b//=g
        nump.append([abs(a),abs(b)])


nump=list(map(tuple,nump))
numm=list(map(tuple,numm))
u=Counter(nump)
v=Counter(numm)


nums=[]
pairs=[]
for k in u.keys():
    vz=((-1)*k[1],k[0])
    s=u[k]
    t=v[vz]
    
    
    
    if t>0:
        nums.append([s,t])
        pairs.append(s+t)





if countx>0 and county>0:
    cou=countx+county
else:
    cou=0
ans=bekit[n-sum(pairs)-cou-countz]

for j in range(len(nums)):
    q=bekit[nums[j][0]]
    p=bekit[nums[j][1]]
    
    
    ans=(ans*(q+p-1))%mod
if countx>0 and county>0:
    ans=(ans*(bekit[countx]+bekit[county]-1))%mod
ans-=1
if countz>0:
    ans+=countz%mod
print(ans%mod)

Solution (Python):
import sys

def main():
    input = sys.stdin.readline
    mod = pow(10,9)+7
    
    n = int(input())
    key1 = dict()
    key2 = dict()
    
    a_0 = 0
    b_0 = 0
    ab_0 = 0
    
    for i in range(n):
        a, b = map(int, input().split())
        if a == 0 and b == 0:
            ab_0 += 1
            continue
        if a == 0:
            a_0 += 1
            continue
        if b == 0:
            b_0 += 1
            continue
        k1, k2 = abs(a), abs(b)
        if k2 < k1:
            k1, k2 = k2, k1
        while k2%k1:
            k2, k1 = k1, k2%k1
        a //= k1
        b //= k1
        if a*b > 0:
            k = (abs(a), abs(b))
            if k in key1:
                key1[k] += 1
            else:
                key1[k] = 1
        else:
            k = (abs(b), abs(a))
            if k in key2:
                key2[k] += 1
            else:
                key2[k] = 1
    
    
    left = n-a_0-b_0-ab_0
    key = [(a_0, b_0)]
    for k, v in key1.items():
        if k in key2:
            v2 = key2[k]
            key.append((v, v2))
            left -= v+v2
    
    ans = pow(2, left, mod)
    for a, b in key:
        ans *= pow(2, a, mod)+pow(2, b, mod)-1
        ans %= mod
    ans += mod-1
    ans += ab_0
    ans %= mod
    
    print(ans)


if __name__ == "__main__":
    main()

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

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(IN())
mod=1000000007



def mk(a,b):
	if a == 0:
		return 0,1
	if b==0:
		return 1,0
		
	c = -1 if a < 0 else 1
	r = math.gcd(abs(a),abs(b))
	ra = (a //r)*c
	rb = (b //r)*c
	
	return ra, rb
	
def mh(a,b):
	return str(a)+'_'+str(b)
	
def mv(s):
	a,b = map(int, s.split('_'))
	return a,b
	
def ty(s):
	a, b = mv(s)
	sign = 1 if b > 0 else -1
	return mh(b*sign, -a*sign)
	

def main():
	n = int(input())
	dd = defaultdict(lambda : 0)
	zero_fish_num=0
	for _ in range(n):
		a,b=tin()
		if a== 0 and b == 0:
			zero_fish_num += 1
			continue
		a,b = mk(a,b)
		dd[mh(a,b)] += 1
		
	cc = set()
	ret = 1
	for k in dd:
		if k in cc:
			continue
		v = dd[k]
		if ty(k) in dd:
			tv = dd[ty(k)]
			r = pow(2,v,mod)+pow(2,tv,mod)-1
			
			ret *= r
			ret %= mod
			cc.add(ty(k))
		else:
			
			ret *= pow(2,v,mod)
			ret %= mod
			
	ret -= 1
	ret += zero_fish_num
	ret %= mod
	print(ret) 
			
		
		
	
	
	
	
	

isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
import sys


MODULO = 1000000007


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

n = int(input())

a_b = [() for i in range(n)]
m_b_a = [() for i in range(n)]




a_b_value_count = {}
m_b_a_value_count = {}

a_b_value_rep = {}
m_b_a_value_rep = {}

used = [False for _ in range(n)]
zeroes = 0
is_zero = [False for _ in range(n)]

for i in range(n):
	a, b = map(int, input().split())

	if a == 0 and b == 0:
		zeroes += 1
		used[i] = True
		is_zero[i] = True
	else:
		if a == 0:
			a_b[i] = (0, 1)
			m_b_a[i] = (1, 0)
		elif b == 0:
			a_b[i] = (1, 0)
			m_b_a[i] = (0, 1)
		else:
			neg = False
			if a*b < 0:
				neg = True
			d = gcd(abs(a), abs(b))
			a = abs(a) // d
			b = abs(b) // d

			if neg:
				a_b[i] = (-a, b)
				m_b_a[i] = (b, a)
			else:
				a_b[i] = (a, b)
				m_b_a[i] = (-b, a)

		a_b_value_count[a_b[i]] = a_b_value_count.get(a_b[i], 0) + 1
		
 
		m_b_a_value_count[m_b_a[i]] = m_b_a_value_count.get(m_b_a[i], 0) + 1
		
		if a_b[i] not in a_b_value_rep:
			a_b_value_rep[a_b[i]] = i
		if m_b_a[i] not in m_b_a_value_rep:
			m_b_a_value_rep[m_b_a[i]] = i

ans = 1
for i in range(n):
	if not is_zero[i] and not used[a_b_value_rep[a_b[i]]]:
		
		if a_b[i] not in m_b_a_value_count:
			ans *= pow(2, a_b_value_count[a_b[i]], MODULO)
			ans %= MODULO
			used[a_b_value_rep[a_b[i]]] = True
			
			
		else:
			s = a_b_value_count[a_b[i]]
			t = m_b_a_value_count[a_b[i]]
			ans *= ((1*pow(2, s, MODULO) + 1*pow(2, t, MODULO) -1) % MODULO)
			ans %= MODULO

			used[a_b_value_rep[a_b[i]]] = True
			used[m_b_a_value_rep[a_b[i]]] = True
			
			
 
			
			
 
 

print((ans-1+zeroes) % MODULO)

Solution (Python):
mod = 10 ** 9 + 7
from math import gcd
N = int(input())
from collections import defaultdict
X = defaultdict(lambda: [0, 0])
x = 0
y = 0
z = 0
for i in range(N):
  a, b = map(int, input().split())
  g = abs(gcd(a, b))
  if a * b > 0:
    X[(abs(a) // g, abs(b) // g)][0] += 1
  elif a * b < 0:
    X[(abs(b) // g, abs(a) // g)][1] += 1
  else:
    if a:
      x += 1
    elif b:
      y += 1
    else:
      z += 1
ans = 1
pow2 = [1]
for i in range(N):
  pow2 += [pow2[-1] * 2 % mod]
for i in X.values():
  ans *= pow2[i[0]] + pow2[i[1]]- 1
  ans %= mod
ans *= pow2[x] + pow2[y] - 1
ans += z - 1
ans %= mod
print(ans)

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

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline
MOD = 10 ** 9 + 7


def solve():
    N = int(rl())
    AB = tuple(tuple(map(int, rl().split())) for _ in range(N))
    
    zero_pare = 0
    zero_a, zero_b = 0, 0
    counter = defaultdict(int)
    for a, b in AB:
        if a == b == 0:
            zero_pare += 1
        elif a == 0:
            zero_a += 1
        elif b == 0:
            zero_b += 1
        else:
            cd = gcd(a, b)
            a, b = a // cd, b // cd
            if b < 0:
                a, b = -a, -b
            counter[(a, b)] += 1
    
    ans = pow(2, zero_a, MOD) + pow(2, zero_b, MOD) - 1
    memo = set()
    for a, b in list(counter):
        if (a, b) in memo:
            continue
        pa, pb = -b, a
        if pb < 0:
            pa, pb = -pa, -pb
        memo.add((a, b))
        memo.add((pa, pb))
        ans *= pow(2, counter[(a, b)], MOD) + pow(2, counter[(pa, pb)], MOD) - 1
        ans %= MOD
    
    ans = (ans + zero_pare - 1) % MOD
    print(ans)


if __name__ == '__main__':
    solve()