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 collections import defaultdict
import math

def main():
    n = int(input())
    mod = 1000000007
    zeroes = 0
    quadrant1 = defaultdict(int)
    quadrant2 = defaultdict(int)

    for _ in range(n):
        a, b = map(int, input().split())
        if a == b == 0:
            zeroes += 1
            continue

        g = math.gcd(a, b)
        a, b = a//g, b//g 
        
        if b < 0:
            a, b = -a, -b
        
        if a <= 0:
            a, b = b, -a
            quadrant1[(a, b)] += 0
            quadrant2[(a, b)] += 1
        else:
            quadrant1[(a, b)] += 1
            quadrant2[(a, b)] += 0
    
    ans = 1
    for key, value in quadrant1.items():
        now = 1
        now += pow(2, value, mod) - 1
        now += pow(2, quadrant2[key], mod) - 1
        ans = (ans * now) % mod
    
    ans += (zeroes - 1)
    return ans % mod

if __name__ == '__main__':
    print (main())

Solution (Python):
from collections import defaultdict
import math


def main():
    n = int(input())
    mod = 1000000007
    zeroes = 0
    counter1 = defaultdict(int)
    counter2 = defaultdict(int)
    for _ in range(n):
        x, y = [int(x) for x in input().split()]

        if x == y == 0:
            zeroes += 1
            continue

        denominator = math.gcd(x, y)
        x, y = x // denominator, y // denominator

        if y < 0:
            
            x, y = -x, -y

        if x <= 0:
            
            x, y = y, -x
            counter2[(x, y)] += 1
            counter1[(x, y)] += 0
        else:
            counter1[(x, y)] += 1
            counter2[(x, y)] += 0

    ans = 1
    for k, v in counter1.items():
        now = 1
        now += pow(2, v, mod) - 1
        now += pow(2, counter2[k], mod) - 1
        ans = ans * now % mod
    ans += zeroes
    ans -= 1  
    return ans % mod


if __name__ == '__main__':
    print(main())

Solution (Python):
from math import gcd
n = int(input())
ab = [list(map(int, input().split())) for _ in range(n)]
mod = 1000000007



kai = [1]*(n+1)
gyaku = [1]*(n+1)

for i in range(2, n+1):
    kai[i] = kai[i-1]*i % mod
    gyaku[i] = gyaku[i-1]*pow(i, mod-2, mod) %mod

azero = 0
bzero = 0
zerozero = 0
dict_patterns = {}
dict_patterns_minus = {}
all_effective = 0
answer = 0
dict_patterns["1,0"] = 0
dict_patterns["0,-1"] = 0

for i in range(n):
    minus = False
    a, b = ab[i]
    if a == 0 and b == 0:
        zerozero += 1
        continue
    elif b == 0:
        dict_patterns["1,0"] += 1
        continue
    elif a == 0:
        dict_patterns["0,-1"] += 1
        continue
    
    common = gcd(a,b)
    a = a//common
    b = b//common
    

    
    if a < 0 and b < 0:
        a = -a
        b = -b
    elif a < 0:
        a = -a
        b = -b
    
    
    to_str = str(a)+","+str(b)
    if to_str not in dict_patterns:
        dict_patterns[to_str] = 1
    else:
        dict_patterns[to_str] += 1


keys = list(dict_patterns.keys())
patterns = []
test = []
for i in range(len(keys)):
    pattern_A = dict_patterns[keys[i]]
    dict_patterns[keys[i]] = 0
    pattern_B = 0
    a, b = map(int, keys[i].split(","))
    
    if str(b)+","+str(-a) in dict_patterns:
        pattern_B += dict_patterns[str(b)+","+str(-a)]
        dict_patterns[str(b)+","+str(-a)] = 0
    if str(-b)+","+str(a) in dict_patterns:
        pattern_B += dict_patterns[str(-b)+","+str(a)]
        dict_patterns[str(-b)+","+str(a)] = 0
    if pattern_A != 0 or pattern_B != 0:
        patterns.append(max(2**pattern_A-1,0) + max(2**pattern_B-1,0)+1)  
    test.append([pattern_A, pattern_B])

answer = 1
for i in range(len(patterns)):
    answer = answer*patterns[i] % mod

print((answer-1+zerozero)%mod)

Solution (Python):
from math import gcd
n = int(input())
ab = [list(map(int, input().split())) for _ in range(n)]
mod = 1000000007



kai = [1]*(n+1)
gyaku = [1]*(n+1)

for i in range(2, n+1):
    kai[i] = kai[i-1]*i % mod
    gyaku[i] = gyaku[i-1]*pow(i, mod-2, mod) %mod

azero = 0
bzero = 0
zerozero = 0
dict_patterns = {}
dict_patterns_minus = {}
all_effective = 0
answer = 0
dict_patterns["1,0"] = 0
dict_patterns["0,-1"] = 0

for i in range(n):
    minus = False
    a, b = ab[i]
    if a == 0 and b == 0:
        zerozero += 1
        continue
    elif b == 0:
        dict_patterns["1,0"] += 1
        continue
    elif a == 0:
        dict_patterns["0,-1"] += 1
        continue
    common = gcd(a,b)
    a, b = int(a//common), int(b//common)
    if a < 0 and b < 0:
        a,b = -a,-b
    elif a < 0:
        a,b = -a,-b
        minus = True
    elif b<0:
        minus = True
    
    to_str = str(a)+","+str(b)
    if to_str not in dict_patterns:
        if minus == False:
            dict_patterns[to_str] = 1
        else:
            dict_patterns[to_str] = 1
    else:
        if minus == False:
            dict_patterns[to_str] += 1
        else:
            dict_patterns[to_str] += 1



keys = list(dict_patterns.keys())
patterns = []
test = []
for i in range(len(keys)):
    pattern_A = dict_patterns[keys[i]]
    dict_patterns[keys[i]] = 0
    pattern_B = 0
    a, b = map(int, keys[i].split(","))
    if str(b)+","+str(-a) in dict_patterns:
        pattern_B += dict_patterns[str(b)+","+str(-a)]
        dict_patterns[str(b)+","+str(-a)] = 0
    elif str(-b)+","+str(a) in dict_patterns:
        pattern_B += dict_patterns[str(-b)+","+str(a)]
        dict_patterns[str(-b)+","+str(a)] = 0
    if pattern_A != 0 or pattern_B != 0:
        patterns.append(max(2**pattern_A-1,0) + max(2**pattern_B-1,0) + 1)  
    test.append([pattern_A, pattern_B])

answer = 1
for i in range(len(patterns)):
    answer = answer*patterns[i] % mod

print((answer-1+zerozero)%mod)

Solution (Python):


import sys
from collections import defaultdict
from math import gcd

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = input()
    it = map(int, sys.stdin.read().split())
    mod = 10**9 + 7

    d1 = [defaultdict(int), defaultdict(int)]
    z0 = za = zb = 0
    for ai, bi in zip(it, it):
        t = ai * bi
        if t == 0:
            if ai != 0:
                za += 1
            elif bi != 0:
                zb += 1
            else:
                z0 += 1
            continue

        ci = gcd(ai, bi)
        ai, bi = ai // ci, bi // ci

        t = t < 0
        if ai < 0:
            ai, bi = -ai ,-bi

        d1[t][(ai, bi)] += 1


    a1, a2 = d1
    ans = 1
    z1 = 0
    for (ai, bi), v in a1.items():
        k2 = (bi, -ai)
        if k2 in a2:
            v2 = a2[k2]
            ans *= pow(2, v, mod) + pow(2, v2, mod) - 1
            ans %= mod
        else:
            z1 += v

    for (ai, bi), v in a2.items():
        k2 = (-bi, ai)

        if k2 in a1: continue

        z1 += v
    ans *= pow(2, za, mod) + pow(2, zb, mod) - 1
    ans %= mod
    ans *= pow(2, z1, mod)

    print((ans-1+z0) % mod)



if __name__ == "__main__":
    resolve()

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

def main():
    mod=1000000007
    n=int(input())
    AB=[tuple(map(int,input().split())) for _ in range(n)]
    Cnt=defaultdict(int)
    zero=0
    for a,b in AB:
        if a==0 and b==0:
            zero+=1
        elif a==0:
            Cnt[(0,1)]+=1
        elif b==0:
            Cnt[(1,0)]+=1
        elif b!=0 and a>0:
            Cnt[(a//gcd(a,b),b//gcd(a,b))]+=1
        else: 
            Cnt[(-a//gcd(a,b),-b//gcd(a,b))]+=1
    ans=1
    for Key in list(Cnt.keys()):
        if Key!=(0,1) and Key!=(1,0):
            a,b=Key
            if b>0:
                ans*=pow(2,Cnt[Key],mod)+pow(2,Cnt[(b,-a)],mod)-1
                ans%=mod
                Cnt[(b,-a)]=0
            else:
                ans*=pow(2,Cnt[Key],mod)+pow(2,Cnt[(-b,a)],mod)-1
                ans%=mod
                Cnt[(-b,a)]=0
            Cnt[Key]=0
        else:
            ans*=pow(2,Cnt[(0,1)],mod)+pow(2,Cnt[(1,0)],mod)-1
            ans%=mod
            Cnt[(0,1)],Cnt[(1,0)]=0,0
    print((ans-1+zero)%mod)
    
if __name__=='__main__':
    main()

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

MOD = 1000000007
N = int(input())
zeros = 0
bads = defaultdict(lambda: [0, 0])
for _ in range(N):
    x, y = map(int, input().split())
    
    if x == 0 and y == 0:
        zeros += 1
        continue
    
    if y < 0 or (y == 0 and x < 0):
        x, y = -x, -y
    g = gcd(x, y)
    x, y = x // g, y // g
    if x > 0:
        bads[(x, y)][0] += 1
    else:
        bads[(y, -x)][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 + zeros - 1) % MOD)

Solution (Python):
from math import gcd
MOD = 10**9+7
N = int(input())
d = {}
zero = 0
for _ in range(N):
    a, b = map(int, input().split())
    if a == b == 0:
        zero += 1
        continue
    
    if b < 0:
        b = -b
        a = -a
    g = gcd(a, b)
    b //= g
    a //= g
    
    if b == 0 and a == -1:
        a = 1

    
    
    if a > 0:
        if (a, b) in d:
            d[(a, b)][0] += 1
        else:
            d[(a, b)] = [1, 0]
    else:
        
        if (b, -a) in d:
            d[(b, -a)][1] += 1
        else:
            d[(b, -a)] = [0, 1]

ans = 1
for (a, b), (k, l) in d.items():
    ans *= (pow(2, k, MOD)-1 + pow(2, l, MOD)-1 + 1)  
    ans %= MOD
ans -= 1
ans += zero
ans %= MOD
print(ans)

Solution (Python):
from collections import Counter
import math

n = int(input())
ab = []
mod = 10**9+7

num_ab0 = 0
num_a0 = 0
num_b0 = 0

for i in range(n):
    A, B = map(int, input().split())
    if A == 0 and B == 0:
        num_ab0 += 1
    elif A == 0:
        num_a0 += 1
    elif B == 0:
        num_b0 += 1
    else:
        g = math.gcd(A, B)
        if A < 0:
            A = -A
            B = -B
        ab.append((A//g, B//g))

c = Counter(ab)

total = 2 ** num_a0 + 2 ** num_b0 - 1
for k, v in c.items():
    if k[1] < 0:
        num = c.get((-k[1], k[0]))
    else:
        num = c.get((k[1], -k[0]))

    if num:
        if k[1] > 0:
            total *= (2 ** v + 2 ** num - 1)
    else:
        total *= 2 ** v

print((total - 1 + num_ab0) % mod)

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


def main():
    MOD = 1000000007

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

    d = defaultdict(int)
    n_zeros = 0

    for a, b in zip(AB[::2], AB[1::2]):
        if a == 0 and b == 0:
            n_zeros += 1
            continue

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

        if a * b > 0 or b == 0:
            c = (abs(a), abs(b))
        else:
            c = (-abs(a), -abs(b))

        d[c] += 1

    ans = 1
    n_not_paired = 0
    for ab, n in d.items():
        ab_pair = (-ab[1], -ab[0])
        if ab_pair in d:
            if ab[0] > 0:
                m = d[ab_pair]
                ans = ans * (pow(2, n, MOD) + pow(2, m, MOD) - 1) % MOD
        else:
            n_not_paired += n

    ans = (ans * pow(2, n_not_paired, MOD) + n_zeros - 1) % MOD
    print(ans)


if __name__ == '__main__':
    main()

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

mod = 10 ** 9 + 7

N, *AB = map(int, open(0).read().split())

def std(a, b):
    if a == 0:
        return (0, int(b != 0))

    g = gcd(a, b)
    a, b = a // g, b // g
    return (a, b) if a > 0 else (-a, -b)

C = Counter(std(a, b) for a, b in zip(*[iter(AB)] * 2))

ans = 1
cnt = 0
for (a, b), v in C.items():
    if b > 0:
        if (b, -a) in C:
            ans *= -1 + pow(2, v, mod) + pow(2, C[(b, -a)], mod)
            ans %= mod
        else:
            cnt += v
    elif (-b, a) not in C:
        cnt += v

ans *= pow(2, cnt, mod)
ans += C[(0, 0)] - 1

print(ans % mod)

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

mod = 10 ** 9 + 7

N, *AB = map(int, open(0).read().split())

def std(a, b):
    if a == 0:
        return (0, int(b != 0))

    g = gcd(a, b)
    a, b = a // g, b // g
    return (a, b) if a > 0 else (-a, -b)

C = Counter()
for a, b in zip(*[iter(AB)] * 2):
    C[std(a, b)] += 1

ans = 1
cnt = 0
for (a, b), v in C.items():
    if b > 0:
        if (b, -a) in C:
            ans *= -1 + pow(2, v, mod) + pow(2, C[(b, -a)], mod)
            ans %= mod
        else:
            cnt += v
    elif (-b, a) not in C:
        cnt += v

ans *= pow(2, cnt, mod)
ans += C[(0, 0)] - 1

print(ans % mod)

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

mod = 10 ** 9 + 7

N, *AB = map(int, open(0).read().split())

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

    g = gcd(a, b)
    a, b = a // g, b // g
    return (a, b) if a > 0 else (-a, -b)

C = Counter()
orig = 0
for a, b in zip(*[iter(AB)] * 2):
    if a == b == 0:
        orig += 1
    else:
        C[std(a, b)] += 1

ans = 1
cnt = 0
for (a, b), v in C.items():
    if b > 0:
        if (b, -a) in C:
            ans *= -1 + pow(2, v, mod) + pow(2, C[(b, -a)], mod)
            ans %= mod
        else:
            cnt += v
    elif (-b, a) not in C:
        cnt += v

ans *= pow(2, cnt, mod)
ans += orig - 1

print(ans % mod)

Solution (Python):
from math import gcd
MOD = 10**9 + 7
MOD_t_MAX = 2*(10**5) + 10

fac  = [None] * MOD_t_MAX
finv = [None] * MOD_t_MAX
inv  = [None] * MOD_t_MAX
def MOD_COM_init():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MOD_t_MAX):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD
def MOD_COM(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD

def main():
    n = int(input())
    iwashi = [list(map(int, input().split())) for _ in range(n)]
    MOD_COM_init()
    ans = pow(2, n, MOD)
    ans -= 1
    ans %= MOD
    dic = {}
    cnt = [0, 0, 0, 0]
    for i in range(n):
        a, b = iwashi[i]
        if a == 0 and b == 0:
            cnt[3] += 1
        elif b == 0:
            cnt[2] += 1
        elif a == 0:
            cnt[1] += 1
        else:
            cnt[0] += 1
            fa, fb = False, False
            if a < 0:
                fa = True
                a *= -1
            if b < 0:
                fb = True
                b *= -1
            c = gcd(a, b)
            a //= c
            b //= c
            if (fa and not fb) or (not fa and fb):
                a *= -1
            tmp = (a, b)
            if tmp in dic:
                dic[tmp] += 1
            else:
                dic[tmp] = 1
    L = 1
    if 0 < cnt[3]:
        p = (pow(2, n-cnt[3], MOD)-1)*MOD_COM(cnt[3], 1)%MOD
        q = 0
        for i in range(2, cnt[3]+1):
            q += MOD_COM(cnt[3], i)
        q *= pow(2, n-cnt[3], MOD)
        ans -= p+q
        ans %= MOD
    if 0 < cnt[1] and 0 < cnt[2]:
        p = (pow(2, cnt[1], MOD)-1) * (pow(2, cnt[2], MOD)-1) % MOD
        p *= pow(2, cnt[0], MOD)
        L *= ((pow(2, cnt[1], MOD)-1) + (pow(2, cnt[2], MOD)-1) + 1) % MOD
        ans -= p
        ans %= MOD
    if 1 < cnt[0]:
        p = 0
        st = set()
        for v in dic.keys():
            if v in st:
                continue
            u = None
            if v[0] > 0 and v[1] > 0:
                u = (-1*v[1], v[0])
            else:
                u = (v[1], -1*v[0])
            x = dic[v]
            y = 0
            if u in dic:
                y = dic[u]
            cnt[0] -= x+y
            q = (pow(2, x, MOD)-1) * (pow(2, y, MOD)-1) * pow(2, cnt[0], MOD) * L % MOD
            p += q
            L *= ((pow(2, x, MOD)-1) + (pow(2, y, MOD)-1) + 1) % MOD
            L %= MOD
            p %= MOD
            st.add(v)
            st.add(u)
        p %= MOD
        ans -= p
        ans %= MOD
    print(ans%MOD)

if __name__ == "__main__":
    main()

Solution (Python):
from math import gcd
MOD = 10**9 + 7
n = int(input())
zero = 0
cnt = dict()
for i 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 or (y == 0 and x < 0):
        x *= -1
        y *= -1
    rot_90 = 1 if x <= 0 else 0
    if rot_90:
        x, y = y, -x
    try:
        cnt[(x, y)][rot_90] += 1
    except KeyError:
        cnt[(x, y)] = [int(not rot_90), rot_90]

ans = 1
for s, t in cnt.values():
    now = 1
    now += (pow(2, s, MOD) - 1) % MOD
    now += (pow(2, t, MOD) - 1) % MOD
    ans *= now
ans -= 1
ans += zero
print(ans % MOD)

Solution (Python):
import math

n=int(input())
D={}
for _ in range(n):
    a,b=map(int, input().split())
    if a==0 and b==0:
        key=(0,0)
    elif a==0:
        key=(0,1)
    elif b==0:
        key=(1,0)
    else:
        if a<0:
            a=-a
            b=-b
        g=math.gcd(a, abs(b))
        key=(a//g, b//g)
    if key not in D:
        D[key]=0
    D[key]+=1

mod=10**9+7
ans=1
zz=0

for k1, v1 in D.items():
    if v1==0:
        continue
    if k1==(0,0):
        zz+=v1
        continue

    if k1[1]>0:
        k2=(k1[1], -k1[0])
    else:
        k2=(-k1[1], k1[0])

    if k2 not in D:
        ans=ans*pow(2, v1, mod)%mod
    else:
        v2=D[k2]
        m=(pow(2, v1, mod)+pow(2, v2, mod)-1)%mod
        ans=ans*m%mod
        D[k2]=0

print((ans+zz-1)%mod)

Solution (Python):
import math

n=int(input())
D={}
for _ in range(n):
    a,b=map(int, input().split())
    if a==0 and b==0:
        key=(0,0)
    elif a==0:
        key=(0,1)
    elif b==0:
        key=(1,0)
    else:
        if a<0:
            a=-a
            b=-b
        g=math.gcd(a, abs(b))
        key=(a//g, b//g)
    if key not in D:
        D[key]=0
    D[key]+=1

mod=10**9+7
ans=1
zz=0

for k1, v1 in D.items():
    if k1==(0,0):
        zz+=v1
        continue
    if v1==0:
        continue

    if k1[1]>0:
        k2=(k1[1], -k1[0])
    else:
        k2=(-k1[1], k1[0])

    if k2 not in D:
        ans=ans*pow(2, v1, mod)%mod
    else:
        v2=D[k2]
        m=(pow(2, v1, mod)+pow(2, v2, mod)-1)%mod
        ans=ans*m%mod
        D[k2]=0

print((ans+zz-1)%mod)

Solution (Python):
def gcd(a,b):
    if b==0 or a == 0  : return a + b
    return gcd(b, a%b)
N = int(input())
d1 = {}
d2 = {}
zero = 0
for _ in range(N):
    A,B = map(int, input().split())
    if A == 0 and B == 0 :
        zero += 1
        continue
    d = gcd(abs(A), abs(B))
    A,B = A//d, B//d
    if B < 0 or (B==0 and A < 0):
        A,B = -A,-B
    if A > 0 :
        if (A,B) not in d1:d1[(A,B)]=0
        d1[(A,B)]+=1
    else :
        if (A,B) not in d2:d2[(A,B)] = 0
        d2[(A,B)] += 1
ret = []
for (x,y),count in d1.items():
    if (-y, x) in d2 :
        ret.append((count, d2[(-y,x)]))
    else :
        ret.append((count, 0))
for (x,y),count in d2.items():
    if (y,-x) not in d1:
        ret.append((count, 0))
mod = 10 ** 9 + 7
ans = 1
for p,q in ret:
    if q == 0 :
        ans *= 2**p
        ans %= mod
    else :
        ans *= (2**p + 2**q -1 )
        ans %= mod
print( (ans - 1 + zero ) % mod )

Solution (Python):
def gcd(a,b):
    if b==0 or a == 0  : return a + b
    return gcd(b, a%b)
N = int(input())
d1 = {}
d2 = {}
zero = 0
for _ in range(N):
    A,B = map(int, input().split())
    if A == 0 and B == 0 :
        zero += 1
        continue
    d = gcd(abs(A), abs(B))
    A,B = A//d, B//d
    if B < 0 or (B==0 and A < 0):
        A,B = -A,-B
    if A > 0 :
        if (A,B) not in d1:d1[(A,B)]=0
        d1[(A,B)]+=1
    else :
        if (A,B) not in d2:d2[(A,B)] = 0
        d2[(A,B)] += 1
ret = []
for (x,y),count in d1.items():
    if (-y, x) in d2 :
        ret.append((count, d2[(-y,x)]))
    else :
        ret.append((count, 0))
for (x,y),count in d2.items():
    if (y,-x) not in d1:
        ret.append((count, 0))
mod = 10 ** 9 + 7
ans = 1
for p,q in ret:
    if q == 0 :
        ans *= 2**p
        ans %= mod
    else :
        ans *= (2**p + 2**q -1 )
        ans %= mod
print( (ans - 1 + zero + mod) % mod )

Solution (Python):
import math
import numpy as np
def main():
    mod = 1000000007
    N = int(input())
    mp = {}
    zero = 0
    for _ in range(N):
        x , y = map(int, input().split())
        if x == 0 and y == 0:
            zero += 1
        else:
            g = math.gcd(x, y)
            x //= g
            y //= g
            rot = 0
            if x == 0:
                y = 1
            else:
                if y == 0:
                    rot = 1
                    x = 0
                    y = 1
                else:
                    if x < 0 and y < 0:
                        x *= -1
                        y *= -1
                    elif x < 0:
                        rot = 1
                        x *= -1
                        x, y = y, x
                    elif y < 0:
                        rot = 1
                        y *= -1
                        x, y = y, x
            if (x, y) not in mp.keys():
                mp[x, y] = [0, 0]
                mp[x, y][rot] = 1
            else:
                mp[x, y][rot] += 1
        
    
    ans = 1
    for (a, b) in mp.keys():
        now = 1
        
        
        now += pow(2, mp[a, b][0], mod) -1 
        now += pow(2, mp[a, b][1], mod) -1
        ans *= now % mod
    ans += zero - 1
    print(ans % mod)
            
if __name__ == '__main__':
    main()

Solution (Python):
import math
N = int(input())
T = []
for i in range(N):
    a = list(map(int, input().split()))
    T.append(a)

mod = 10**9+7

A = {}
c_zero = 0
a_zero = 0
b_zero = 0
for i in range(N):
    if T[i][0] == 0 and T[i][1] == 0:
        c_zero += 1
    elif T[i][0] == 0:
        a_zero += 1
    elif T[i][1] == 0:
        b_zero += 1
    else:
        t = math.gcd(abs(T[i][0]),abs(T[i][1]))
        c = 0
        if T[i][0] < 0:
            T[i][0] *= -1
            c += 1
        if T[i][1] < 0:
            T[i][1] *= -1
            c += 1
        if (T[i][0]//t,T[i][1]//t,c%2) in A:
            A[T[i][0]//t,T[i][1]//t,c%2] += 1
        else:
            A[T[i][0]//t,T[i][1]//t,c%2] = 1

used = {}
for i in A.keys():
    used[i] = 0

ans = 1
for k,v in A.items():
    if used[k] == 0:
        if k[2] == 1:
            p = A.get((k[1],k[0],0),0)
            if p != 0:
                used[(k[1],k[0],0)] = 1
        else:
            p = A.get((k[1],k[0],1),0)
            if p != 0:
                used[(k[1],k[0],1)] = 1
        ans *= ( pow(2,v,mod)+pow(2,p,mod) - 1 )
        ans %= mod

ans *= ( pow(2,a_zero,mod)+pow(2,b_zero,mod) - 1 )
ans += c_zero
ans -= 1
print(ans%mod)

Solution (Python):



import math


def solve():
    N = int(input())
    ABs = [[int(i) for i in input().split()] for _ in range(N)]
    mod = 10 ** 9 + 7

    lonlieness = 0
    pairs = {}
    for AB in ABs:
        a, b = AB
        if a == 0 and b == 0:
            lonlieness += 1
            continue
        elif a == 0:
            a, b = -1, 0
            bad_a, bad_b = 0, 1
        elif b == 0:
            a, b = (0, 1)
            bad_a, bad_b = -1, 0
        else:
            _gcd = math.gcd(a, b)
            a //= _gcd
            b //= _gcd
            bad_a = -b
            bad_b = a
            if b < 0:
                a, b = -a, -b
            if bad_b < 0:
                bad_a, bad_b = -bad_a, -bad_b
        pairs.setdefault((a, b), 0)
        pairs.setdefault((bad_a, bad_b), 0)  
        pairs[(a, b)] += 1

    permutations = []
    for i, pair in enumerate(pairs.keys()):
        if i % 2 == 1:
            continue  
        a, b = pair
        bad_a, bad_b = -b, a
        if bad_b < 0:
            bad_a, bad_b = -bad_a, -bad_b
        
        
        group_num = pow(2, pairs[(a, b)], mod) - 1
        badgroup_num = pow(2, pairs[(bad_a, bad_b)], mod) - 1
        permutations.append(group_num + badgroup_num + 1)

    result = 1
    for p in permutations:
        result = result * p % mod

    
    result = (result + lonlieness - 1) % mod
    print(result)


if __name__ == '__main__':
    solve()

Solution (Python):



import math


def solve():
    N = int(input())
    ABs = [[int(i) for i in input().split()] for _ in range(N)]
    mod = 10 ** 9 + 7

    lonlieness = 0
    pairs = {}
    for AB in ABs:
        a, b = AB
        if a == 0 and b == 0:
            lonlieness += 1
            continue
        elif a == 0:
            a, b = -1, 0
            bad_a, bad_b = 0, 1
        elif b == 0:
            a, b = (0, 1)
            bad_a, bad_b = -1, 0
        else:
            _gcd = math.gcd(a, b)
            a //= _gcd
            b //= _gcd
            bad_a = -b
            bad_b = a
            if b < 0:
                a, b = -a, -b
            if bad_b < 0:
                bad_a, bad_b = -bad_a, -bad_b
        pairs.setdefault((a, b), 0)
        pairs.setdefault((bad_a, bad_b), 0)  
        pairs[(a, b)] += 1

    permutations = []
    for i, pair in enumerate(pairs.keys()):
        if i % 2 == 1:
            continue
        a, b = pair
        bad_a, bad_b = -b, a
        if bad_b < 0:
            bad_a, bad_b = -bad_a, -bad_b
        group_num = pow(2, pairs[(a, b)], mod) - 1
        badgroup_num = pow(2, pairs[(bad_a, bad_b)], mod) - 1
        permutations.append(group_num + badgroup_num + 1)

    result = 1
    for p in permutations:
        result = result * p % mod

    result = (result + lonlieness - 1) % mod
    print(result)


if __name__ == '__main__':
    solve()

Solution (Python):
from collections import defaultdict
import math

N = int(input())
d_ab = defaultdict(int)
d_ba = defaultdict(int)
mod = 1000000007
a0 = 0
b0 = 0
all0 = 0

for i in range(N):
    A,B = map(int,input().split())
    if A == 0 and B == 0:
        all0 += 1
    elif A == 0:
        a0 += 1
    elif B == 0:
        b0 += 1
    else:
        gcd = math.gcd(A,B)
        if (A < 0 and B > 0) or (A > 0 and B < 0):
            minus_f = True
        else:
            minus_f = False
        A //= gcd
        B //= gcd
        A = abs(A)
        B = abs(B)
        if minus_f:
            d_ab[(-A,B)] += 1
            d_ba[(B,A)] += 1
        else:
            d_ab[(A,B)] += 1
            d_ba[(-B,A)] += 1
        

ans = 1




pairs = list(map(list,d_ab.keys()))
visited = defaultdict(int)


for pair in pairs:
    ab = d_ab[tuple(pair)]
    ba = d_ba[tuple(pair)]
    r_pair = list(reversed(pair))
    if r_pair[0] > 0 and r_pair[1] > 0:
        r_pair[0] *= -1
    elif r_pair[1] < 0:
        r_pair[1] *= -1
    r_pair = tuple(r_pair)
    if ba != 0 and visited[tuple(pair)] == 0:
        visited[r_pair] = 1
        ans *= (pow(2,ab)+pow(2,ba)-1)
        ans %= mod
    if ba == 0 and visited[tuple(pair)] == 0:
        ans *= (pow(2,ab))
        ans %= mod



ans *= (pow(2,a0)+pow(2,b0)-1)
ans %= mod

ans += all0 -1
ans %= mod

print(ans)

Solution (Python):
from collections import defaultdict

MOD = (10 ** 9) + 7
assert MOD == 1000000007

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

n = int(raw_input())

ns = []
d = defaultdict(int)
zero = 0

for i in xrange(n):
    a, b = map(int, raw_input().split())
    ns.append((a, b))
    if a and b:
        s = 1 if a * b >= 0 else -1
        g = gcd(abs(a), abs(b))
        m1 = (s * abs(a) / g, abs(b) / g)
        m2 = (-s * abs(b) / g, abs(a) / g)
    elif a == 0 and b == 0:
        zero += 1
        continue
    elif a == 0:
        m1 = (1, 0)
        m2 = (0, 1)
    elif b == 0:
        m1 = (0, 1)
        m2 = (1, 0)

    d[m1] += 1
    d[m2] += 0

'''
res = 0
for i in xrange(1 << n):
    fs = []
    flag = True
    for j in xrange(n):
        if i & (1 << j):
            fs.append(ns[j])
    for i, f1 in enumerate(fs):
        for f2 in fs[i + 1:]:
            (a1, b1) = f1
            (a2, b2) = f2
            if a1 * a2 + b1 * b2 == 0:
                flag = False
                break
        if not flag:
            break
    if flag:
        res += 1
print res - 1
'''

pre = 1
for k in d.keys():
    if k[0] <= 0:
        assert (k[1], -k[0]) in d
        continue
    else:
        k1 = k
        k2 = (-k[1], k[0])

        tot = pow(2, d[k1], MOD) + pow(2, d[k2], MOD) - 1
        pre = pre * tot % MOD
print (pre - 1 + zero + MOD) % MOD

Solution (Python):

from math import gcd
N=int(input())

mod=1000000007
ans=1
P=dict()
M=dict()
zero=0
zero1=0
zero2=0
for i in range(N):
    a,b=map(int,input().split())
    if a==0 and b==0:
        zero+=1
    elif a==0 and b!=0:
        zero1+=1
    elif a!=0 and b==0:
        zero2+=1
    elif (a>0 and b<0) or (a<0 and b>0):
        GCD=gcd(abs(a),abs(b))
        a=abs(a)//GCD
        b=abs(b)//GCD
        s=str(a)+"/"+str(b)
        P[s]=P.get(s,0)+1
        
    else:
        GCD=gcd(abs(a),abs(b))
        a=abs(a)//GCD
        b=abs(b)//GCD
        s=str(b)+"/"+str(a)
        M[s]=M.get(s,0)+1

P["0/0"]=zero1
M["0/0"]=zero2
for v,cnt_p in P.items():
    if v in M:
        cnt_m=M[v]
        ans*=(2**cnt_p+2**cnt_m-1)
        M.pop(v)
    else:
        ans*=2**cnt_p
    ans%=mod
    
for v,cnt_m in M.items():
    ans*=2**cnt_m
    ans%=mod

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

Solution (Python):
def resolve():
    import math
    from math import gcd
    MOD=10**9+7
    n=int(input())
    zero=0
    cnt={}
    for i in range(n):
        a,b=map(int,input().split())
        if a==0 and b==0:
            zero+=1
            continue
        g=gcd(a,b)
        a//=g
        b//=g
        if b<0:
            a*=-1
            b*=-1
        if b==0 and a<0:
            a*=-1
        if a<=0:
            a,b=b,-a
            if (a,b) in cnt:
                cnt[(a,b)][0]+=1
            else:
                cnt[(a,b)]=[1,0]
        else:
            if (a,b) in cnt:
                cnt[(a,b)][1]+=1
            else:
                cnt[(a,b)]=[0,1]
    ans=1
    for i,v in cnt.items():
        ans*=pow(2,v[0],MOD)+pow(2,v[1],MOD)-1
        ans%=MOD
    print((zero-1+ans)%MOD)    

if __name__ == '__main__':
    resolve()