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



Sample input:
3
1 2
-1 1
2 -1


Sample output:
5

Submission status: Runtime Error

Solution code:
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(b), -abs(a))

        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:
                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()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
#%%code
import random
import math
from collections import  Counter
def resolve():
    MOD=1000000007
    N,=pin()
    #think of Ai*Bi+Aj*Bj=0 "<=" Ai/Bi=0-Bj/Aj　逆は成り立たないのでコーナーケースが出ますね？
    #わかるArctanしたいが考えるな　
    vec=dict()
    vec.setdefault(0,0)
    vec.setdefault("INF",0)
    ori=0
    for i in range(N):
        a,b=pin()
        if b==0:
            if a==0:
                ori+=1
            else:#正負関係なしINF
                vec.setdefault("INF",0)
                vec["INF"]+=1
        if b!=0 and a==0:
            vec.setdefault(0,0)
            vec[0]+=1
        else:
            g=math.gcd(a,b)
            a,b=(a//g,b//g)
            if b<0 and a>0:
                a,b=-a,-b
            f=(a,b)
            vec.setdefault(f,0)
            vec[f]+=1
    n=len(vec)
    #print(vec,n)    
    reg=0    
    banpair=[]
    seen=set()

    for k,v in vec.items():
        if k in seen:
            continue

            
        if k=="INF":#0のペア
            if 0 in vec:
                banpair.append((v,vec[0]))
                seen.add(0)
                continue
                
        elif k==0:
            if "INF" in vec:
                banpair.append((v,vec["INF"]))
                seen.add("INF")
                continue
                
        
        x,y=k
        t=(-y,x)
        if x<0:
            t=(y,-x)
        #print(t)
        if t in vec:
            banpair.append((v,vec[t]))
            seen.add(t)
            continue
        else:
            #print(k,v,"reg")
            reg+=v

    #print(banpair)
    lenb=len(banpair)
    stack=[(0,1)]
    bans=1 
    if banpair!=[]:
        for b in banpair:
            p=pow(2,b[0],MOD)-1
            q=pow(2,b[1],MOD)-1
            bans=bans*(p+q+1)%MOD
    #    #print(bans)
    """
    while(stack!=[]):
        p,q=stack.pop()
        if p==lenb:
            q2=q%MOD
            bans+=q2
            bans%=MOD
            continue
        for i in range(2):
            stack.append((p+1,q*(2**banpair[p][i]-1)%MOD))
        stack.append((p+1,q*1))
    """
    #print(bans,reg)
    #print(N-reg-bans)
    ans1=pow(2,reg,MOD)*(bans)-1
    ans2=(ori)#ori同士も内積のルールに引っかかる
    print((ans1+ans2)%MOD)   
#%%submit!
resolve()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
#%%code
import random
import math
from collections import  Counter
def resolve():
    MOD=1000000007
    N,=pin()
    #think of Ai*Bi+Aj*Bj=0 "<=" Ai/Bi=0-Bj/Aj　逆は成り立たないのでコーナーケースが出ますね？
    #わかるArctanしたいが考えるな　
    vec=dict()
    ori=0
    for i in range(N):
        a,b=pin()
        if b==0:
            if a==0:
                ori+=1
            else:#正負関係なしINF
                vec.setdefault("INF",0)
                vec["INF"]+=1
        if b!=0 and a==0:
            vec.setdefault(0,0)
            vec[0]+=1
        else:
            g=math.gcd(a,b)
            a,b=(a//g,b//g)
            if b<0 and a>0:
                a,b=-a,-b
            f=(a,b)
            vec.setdefault(f,0)
            vec[f]+=1
    n=len(vec)
    #print(vec,n)    
    reg=0    
    banpair=[]
    seen=set()

    for k,v in vec.items():
        if k in seen:
            continue

            
        if k=="INF":#0のペア
            if 0 in vec:
                banpair.append((v,vec[0]))
                seen.add(0)
                continue
                
        elif k==0:
            if "INF" in vec:
                banpair.append((v,vec["INF"]))
                seen.add("INF")
                continue
                
        
        x,y=k
        t=(-y,x)
        if x<0:
            t=(y,-x)
        #print(t)
        if t in vec:
            banpair.append((v,vec[t]))
            seen.add(t)
            continue
        else:
            #print(k,v,"reg")
            reg+=v

    #print(banpair)
    lenb=len(banpair)
    stack=[(0,1)]
    bans=1 
    if banpair!=[]:
        for b in banpair:
            p=pow(2,b[0],MOD)-1
            q=pow(2,b[1],MOD)-1
            bans=bans*(p+q+1)%MOD
    #    #print(bans)
    """
    while(stack!=[]):
        p,q=stack.pop()
        if p==lenb:
            q2=q%MOD
            bans+=q2
            bans%=MOD
            continue
        for i in range(2):
            stack.append((p+1,q*(2**banpair[p][i]-1)%MOD))
        stack.append((p+1,q*1))
    """
    #print(bans,reg)
    #print(N-reg-bans)
    ans1=pow(2,reg,MOD)*(bans)-1
    ans2=(ori)#ori同士も内積のルールに引っかかる
    print((ans1+ans2)%MOD)   
#%%submit!
resolve()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
#%%code
import random
import math
from collections import  Counter
def resolve():
    MOD=1000000007
    N,=pin()
    #think of Ai*Bi+Aj*Bj=0 "<=" Ai/Bi=0-Bj/Aj　逆は成り立たないのでコーナーケースが出ますね？
    #わかるArctanしたいが考えるな　
    vec=dict()
    ori=0
    for i in range(N):
        a,b=pin()
        if b==0:
            if a==0:
                ori+=1
            else:#正負関係なしINF
                vec.setdefault("INF",0)
                vec["INF"]+=1
        if b!=0 and a==0:
            vec.setdefault(0,0)
            vec[0]+=1
        else:
            g=math.gcd(a,b)
            a,b=(a//g,b//g)
            if b<0 and a>0:
                a,b=-a,-b
            f=(a,b)
            vec.setdefault(f,0)
            vec[f]+=1
    n=len(vec)
    ##print(vec,n)    
    reg=0    
    banpair=[]
    seen=set()

    for k,v in vec.items():
        if k in seen:
            continue

            
        if k=="INF":#0のペア
            if 0 in vec:
                banpair.append((v,vec[0]))
                seen.add(0)
                continue
                
        elif k==0:
            if "INF" in vec:
                banpair.append((v,vec["INF"]))
                seen.add("INF")
                continue
                
        
        x,y=k
        t=(-y,x)
        #print(t)
        if t in vec:
            banpair.append((v,vec[t]))
            seen.add(t)
            continue
        else:
            #print(k,v,"reg")
            reg+=v

    #print(banpair)
    lenb=len(banpair)
    stack=[(0,1)]
    bans=1 
    for b in banpair:
        p=pow(2,b[0],MOD)-1
        q=pow(2,b[1],MOD)-1
        bans=bans*(p+q+1)%MOD
#    #print(bans)
    """
    while(stack!=[]):
        p,q=stack.pop()
        if p==lenb:
            q2=q%MOD
            bans+=q2
            bans%=MOD
            continue
        for i in range(2):
            stack.append((p+1,q*(2**banpair[p][i]-1)%MOD))
        stack.append((p+1,q*1))
    """
    #print(bans,reg)
    ##print(N-reg-bans)
    ans1=pow(2,reg,MOD)*(bans)-1
    ans2=(ori)#ori同士も内積のルールに引っかかる
    print((ans1+ans2)%MOD)   
#%%submit!
resolve()

Submission status: Runtime Error

Solution code:
# 解説と 13355391 を参考に実装予定


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

Submission status: Runtime Error

Solution code:
from collections import defaultdict

MOD = (10 ** 9) + 7

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

n = int(raw_input())

ns = []
d = defaultdict(int)

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:
        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 f1 in fs:
        for f2 in fs:
            (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
    elif k[0] == 0:
        pre = pre * d[k] % MOD
    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 + MOD) % MOD

Submission status: Runtime Error

Solution code:
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()

Submission status: Runtime Error

Solution code:
from collections import defaultdict

MOD = (10 ** 9) + 7

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

n = int(raw_input())

ns = []
d = defaultdict(int)

for i in xrange(n):
    a, b = map(int, raw_input().split())
    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)
    d[m1] += 1
    d[m2] += 0

pre = 1
for k in d.keys():
    if k[0] < 0:
        continue
    elif k[0] == 0:
        pre = pre * d[k] % MOD
    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 + MOD) % MOD

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import math


def main():
    n = int(input())
    mod = 1000000007
    zeroes = 0
    counter = defaultdict(lambda: defaultdict(int))
    for _ in range(n):
        a, b = [int(x) for x in input().split()]
        denominator = math.gcd(a, b)
        x, y = a // denominator, b // denominator

        if x == y == 0:
            zeroes += 1
            continue
        if y < 0:
            # quadrant III, IV -> I, II
            x, y = -x, -y

        if x <= 0:
            # round 90° from quadrant II to I
            x, y = y, -x
            counter[(x, y)][1] += 1
        else:
            counter[(x, y)][0] += 1

    ans = 1
    for v in counter.values():
        now = 1
        now += pow(2, v[0], mod) - 1
        now += pow(2, v[1], mod) - 1
        ans = ans * now % mod
    ans += zeroes
    ans -= 1  # choose no fish
    return ans % mod


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

Submission status: Runtime Error

Solution code:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N = int(input())

d = {}
zeros = 0

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

    return a

MOD = int(1e9) + 7
p = [1] * (N + 1)
for i in range(N):
    p[i + 1] = p[i] * 2 % MOD
    a, b = map(int, input().split())
    if a == b == 0:
        zeros += 1
        continue
    a, b = a // gcd(a, b), b // gcd(a, b)

    if a == 0:
        f, s = d.get((a, abs(b)), (0, 0))
        d[(a, abs(b))] = (f + 1, s)

    if b == 0:
        f, s = d.get((b, abs(a)), (0, 0))
        d[(b, abs(a))] = (f, s + 1)

    if a < 0 or b < 0:
        if a < 0:
            a, b = -a, -b
        f, s = d.get((abs(b), a), (0, 0))
        d[(abs(b), a)] = (f, s + 1)
    else:
        f, s = d.get((abs(a), abs(b)), (0, 0))
        d[(abs(a), abs(b))] = (f + 1, s)

ans = 1
for _, (f, s) in d.items():
    cnt = p[f] - 1
    cnt += p[s] - 1
    cnt += 1
    cnt %= MOD
    ans *= cnt
    ans %= MOD

ans -= 1
ans += zeros
print(ans)

Submission status: Runtime Error

Solution code:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N = int(input())

d = {}
zeros = 0

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

    return a

MOD = int(1e9) + 7
p = [1] * (N + 1)
for i in range(N):
    p[i + 1] = p[i] * 2 % MOD
    if a == b == 0:
        zeros += 1
        continue
    a, b = map(int, input().split())
    a, b = a // gcd(a, b), b // gcd(a, b)

    if a == 0:
        f, s = d.get((a, abs(b)), (0, 0))
        d[(a, abs(b))] = (f + 1, s)

    if b == 0:
        f, s = d.get((b, abs(a)), (0, 0))
        d[(b, abs(a))] = (f, s + 1)

    if a < 0 or b < 0:
        if a < 0:
            a, b = -a, -b
        f, s = d.get((abs(b), a), (0, 0))
        d[(abs(b), a)] = (f, s + 1)
    else:
        f, s = d.get((abs(a), abs(b)), (0, 0))
        d[(abs(a), abs(b))] = (f + 1, s)

ans = 1
for _, (f, s) in d.items():
    cnt = p[f] - 1
    cnt += p[s] - 1
    cnt += 1
    cnt %= MOD
    ans *= cnt
    ans %= MOD

ans -= 1
ans += zeros
print(ans)

Submission status: Runtime Error

Solution code:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N = int(input())

d = {}
zeros = 0

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

    return a

MOD = int(1e9) + 7
p = [1] * (N + 1)
for i in range(N):
    p[i + 1] = p[i] * 2 % MOD
    a, b = map(int, input().split())
    a, b = a // gcd(a, b), b // gcd(a, b)
    if a == b == 0:
        zeros += 1
        continue

    if a == 0:
        f, s = d.get((a, abs(b)), (0, 0))
        d[(a, abs(b))] = (f + 1, s)

    if b == 0:
        f, s = d.get((b, abs(a)), (0, 0))
        d[(b, abs(a))] = (f, s + 1)

    if a < 0 or b < 0:
        if a < 0:
            a, b = -a, -b
        f, s = d.get((abs(b), a), (0, 0))
        d[(abs(b), a)] = (f, s + 1)
    else:
        f, s = d.get((abs(a), abs(b)), (0, 0))
        d[(abs(a), abs(b))] = (f + 1, s)

ans = 1
for _, (f, s) in d.items():
    cnt = p[f] - 1
    cnt += p[s] - 1
    cnt += 1
    cnt %= MOD
    ans *= cnt
    ans %= MOD

ans -= 1
ans += zeros
print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
ab=[list(map(int,input().split())) for _ in range(n)]
d={}
mod=10**9+7
def gcd(x,y):
    if x==y:
        return x
    elif x>y:
        r=-1
        while r!=0:
            r=x%y
            x=y
            y=r
        return x
    else:
        r=-1
        while r!=0:
            r=y%x
            y=x
            x=r
        return y
z=0
for i in range(n):
    a,b=ab[i]
    if a==0 and b==0:
        z+=1
        continue
    x=gcd(a,b)
    a//=x
    b//=x
    if a<0:
        a*=-1
        b*=-1
    if a==0:
        b=1
    if b==0:
        a=1
    y=(a,b)
    if y in d:
        d[y]+=1
    else:
        d[y]=1
ans=1
re={}
for t,v in d.items():
    if t in re:
        continue
    a,b=t
    c=0
    if (b,-a) in d:
        c+=d[(b,-a)]
        re[(b,-a)]=1
    if (-b,a) in d:
        c+=d[(-b,a)]
        re[(-b,a)]=1
    ans*=(2**v-1+2**c-1+1)
    ans%=mod
ans-=1
ans+=z
ans%=mod
print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
ab=[list(map(int,input().split())) for _ in range(n)]
d={}
mod=10**9+7
def gcd(x,y):
    if x==y:
        return x
    elif x>y:
        r=-1
        while r!=0:
            r=x%y
            x=y
            y=r
        return x
    else:
        r=-1
        while r!=0:
            r=y%x
            y=x
            x=r
        return y

for i in range(n):
    a,b=ab[i]
    x=gcd(a,b)
    a//=x
    b//=x
    if a<0:
        a*=-1
        b*=-1
    if a==0:
        b=1
    if b==0:
        a=1
    y=(a,b)
    if y in d:
        d[y]+=1
    else:
        d[y]=1
z=0
if (0,0) in d:
    z=d[(0,0)]
ans=1
re={}
for t,v in d.items():
    if t in re:
        continue
    a,b=t
    c=0
    if (b,-a) in d:
        c+=d[(b,-a)]
        re[(b,-a)]=1
    if (-b,a) in d:
        c+=d[(-b,a)]
        re[(-b,a)]=1
    ans*=(2**v-1+2**c-1+1)
    ans%=mod
ans-=1
ans+=z
ans%=mod
print(ans)

Submission status: Runtime Error

Solution code:
import math
from collections import defaultdict

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

MOD = 10 * 9 + 7
d = defaultdict(int)
zero = 0
N = INP()
print(N)
for _ in range(N):
    A,B = LINP()
    if A == 0 and B == 0:
        zero += 1
        continue
    A = int(A/math.gcd(A,B))
    B = int(B/math.gcd(A,B))
    minus = (-1) ** ((A < 0) + (B < 0))
    d[(minus * abs(A), abs(B))] += 1

ans = 1
seen = set()
for a, b in d:
    if (a, b) not in seen:
        if(a, b) in [(0, 1), (1, 0)]:
            ainv, binv = b, a
        else:
            ainv, binv = b * (1 if a < 0 else -1), abs(a)
        new_ans = (2 ** d[(a, b)] - 1)
        new_ans *= (2 ** d[(ainv, binv)] -1) if d.get(ainv, binv) != None else 0
        new_ans += 1
        ans *= new_ans % MOD
        seen.add((a, b))
        seen.add((ainv, binv))
ans = (ans + zero) & MOD
print(ans)

Submission status: Runtime Error

Solution code:
from collections import Counter

mod = 10**9 + 7

N = int(input())

A_B = [0] * N

for i in range(N):
    A, B = map(int, input().split())
    A_B[i] = A / B

c_ab = Counter(A_B)
keys = list(c_ab.keys())
found = [False] * len(keys)

ans = 1

ans = ans * pow(2,(c_ab[0] + c_ab[float("inf")]), mod)

for i in range(len(keys)):
    if int(keys[i]) == 0 or keys[i] == float("inf"):
        found[i] == True

    for j in range(i+1, len(keys)):
        if keys[i] * keys[j] == -1:
            found[i], found[j] = True, True
            tmp = pow(2, c_ab[keys[i]], mod) + pow(2, c_ab[keys[j]], mod) - 1
            ans = ans * tmp % mod

r = 0

for i in range(len(keys)):
    if not found[i]:
        r += c_ab[keys[i]]

ans = ans * pow(2,r,mod) % mod - 1

print(ans)

Submission status: Runtime Error

Solution code:
from math import gcd
from numpy import sign
mod = 1000000007
N = int(input())

if N == 1:
    print(1)
    
d = {}

search_list = []

for _ in range(N):
    a, b = list(map(int, input().split()))
    if a == b == 0:
        if (0, 0) not in d:
            d[(0, 0)] = 1
        else:
            d[(0, 0)] += 1
    else:
        g = gcd(a, b)

        a, b =  a / g, b /g
        if b < 0:
            a, b = -a, -b
        if b == 0:
            a, b =  1, 0
        if (a, b) not in d:
            d[(a, b)] =1
        else:
            d[(a, b)] +=1

answer = 1



for k in list(d.keys()):
    if k not in done_list and k != (0, 0):
        pair_k = (sign(k[0]) * (-1) * k[1], abs(k[0]))
        if pair_k not in d:
            answer *= (2 ** d[k]) % mod
            answer = answer % mod
            done_list += [k]
        else:
            answer *= ((2 ** d[k]) + (2 ** d[pair_k]) - 1) % mod
            answer = answer % mod
            done_list += [k, pair_k]

if (0, 0) in d:
    answer += d[(0, 0)]
    
print((answer - 1) % mod)

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.buffer.readline
mod=10**9+7
n=int(input())
d={}
z=0
from math import gcd 
for i in range(n):
    x,y=map(int,input().split())
    if x==y==0:z+=1
    else:
        f=gcd(x,y)
        x//=f;y//=f
        if x<0:x*=-1;y*=-1
        if x==0 and y<0:y=-y
        d[(x,y)]=1 if (x,y)not in d else d[(x,y)]+=1
ans=1
for (a,s) in d:
    if d[(a,s)]==0:continue
    ng=0
    if (s,-a)in d:ng+=d[(s,-a)];d[(s,-a)]=0
    if (-s,a)in d:ng+=d[(-s,a)];d[(-s,a)]=0
    ans*=(pow(2,d[(a,s)],mod)-1 + pow(2,ng,mod)-1 +1)%mod
    ans%=mod
    d[(a,s)]=0
print((ans+z-1)%mod)

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.buffer.readline
mod=10**9+7
n=int(input())
d={}
z=0
from math import gcd 
for i in range(n):
    x,y=map(int,input().split())
    if x==y==0:z+=1
    else:
        f=gcd(x,y)
        x//=f;y//=f
        if x<0:x*=-1;y*=-1
        if x==0 and y<0:y=-y
        d[(x,y)]+=1 if (x,y)in d else d[(x,y)]=1
ans=1
for (a,s) in d:
    if d[(a,s)]==0:continue
    ng=0
    if (s,-a)in d:ng+=d[(s,-a)];d[(s,-a)]=0
    if (-s,a)in d:ng+=d[(-s,a)];d[(-s,a)]=0
    ans*=(pow(2,d[(a,s)],mod)-1 + pow(2,ng,mod)-1 +1)%mod
    ans%=mod
    d[(a,s)]=0
print((ans+z-1)%mod)

Submission status: Runtime Error

Solution code:
from fractions import gcd

N=int(input())
d={}
#l=[]
MOD = 1000000007
nz=0
for _ in range(N):
    a,b=map(int,input().split())
    if a==0 and b==0:
        nz+=1
        #p=(0,0)
    elif a==0:
        p=(0,1)
    elif b==0:
        p=(1,0)
    else:
        c=gcd(a,b)
        if b > 0:
            p=(a//c,b//c)
        else: # b < 0
            p=(-a//c,-b//c)
    
    #l.append(p)
    if p in d:
        d[p]+=1
    else:
        d[p] = 1

ans=1
#for p in l:
while len(d) > 0:
    p,np=d.popitem()
    if p==(1,0):
        q=(0,1)
    elif p==(0,1):
        q=(1,0)
    else:
        pa,pb=p
        if pa > 0:
            q=(-pb,pa)
        else: #pa < 0
            q=(pb,-pa)
    if q in d:
        nq=d.pop(q)
    else:
        nq=0
    
    ans *= ((2**np + 2**nq - 1) % MOD)
    ans %= MOD

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

Submission status: Runtime Error

Solution code:
import math

N = int(input())
mod = 1000000007
dic = {} #{[2,3]:[正の数,負の数]}
zero = 0
dic[0,1] = [0,0]

#辞書登録
for i in range(N):
    A,B = list(map(int,input().split()))

    if(A == 0 and B == 0):
        zero += 1
        continue
    elif(A == 0 and B != 0):
        dic[[0,1]][0] += 1
        continue
    elif(A != 0 and B == 0):
        dic[[0,1]][1] += 1
        continue

    if(A*B < 0):
        A = (-1) * abs(A)
    else:
        A = abs(A)
    B = abs(B)
    As /= gcd(A,B)
    Bs /= gcd(A,B)
    if(A*B < 0):
        if([B,abs(A)] in dic):
            dic[[B,abs(A)]][1] += 1
        else:
            dic[[B,abs(A)]] = [0,1]
    else:
        if([A,B] in dic):
            dic[[A,B]][0] += 1
        else:
            dic[[A,B]] = [1,0]

cnt_iso = 0
ans = 1

#ペアになってない数
for key in dic.key:
    if(key[0] == 0):
        cnt_iso += key[1]
    elif(key[1] == 0):
        cnt_iso += key[1]

ans *= 2**cnt_iso % mod

for key in dic.key:
    if(key[0] != 0 and key[1] != 0):
        ans *= (2**key[0] + 2**key[1]) % mod

print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(300000)
from fractions import gcd
from collections import defaultdict

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


N = I()
d = defaultdict(int)
for i in range(N):
    a, b = MI()
    g = gcd(a, b)
    a, b = a // g, b // g
    minus = (-1) ** ((a < 0) + (b < 0))
    d[(minus * abs(a), abs(b))] += 1

ans = 1
seen = set()
for a, b in d:
    if (a, b) not in seen:
        ainv, binv = b * (1 if a < 0 else -1), abs(a)
        lans = (2 ** d[(a, b)] - 1)
        lans += (2 ** d[(ainv, binv)] - 1) if d.get((ainv, binv)) is not None else 0
        lans += 1
        ans = ans * lans % MOD
        seen.add((a, b))
        seen.add((ainv, binv))
print((ans + MOD - 1) % MOD)

Submission status: Runtime Error

Solution code:
# E - ∙ (Bullet)
import sys
from collections import defaultdict

readline = sys.stdin.readline
MOD = 1000000007
N = int(readline())

# イワシの傾きをA/Bとする。
# A/Bは予めgcdで割って約分し、同じ傾きのものを揃えておく。
# このとき、仲の悪い組合せは(A, B)に対して(B, -A)となるもの。 
# 前者をS、後者をTとして考える。
d_S = defaultdict(int)
d_T = defaultdict(int)

def gcd(x, y):
    if x == 0:
        return y
    else:
        return gcd(y%x, x)

pow2_mod = [1] + [0] * (N-1)
for i in range(1, N):
    pow2_mod[i] = pow2_mod[i-1] * 2 % MOD

zeros = 0
for i in range(N):
    A, B = map(int, readline().split())
    # (0, 0)のイワシは他の全てのイワシと仲が悪いため、
    # 1匹のみでしか選ぶことができない。最後にこの数を足す。
    if A == 0 and B == 0:
        zeros += 1
    # (?, 0),(0, ?)のイワシは、?がどのような数字であろうとも
    # この組合せであれば仲が悪い。一律、(1,0)(0,-1)として考える。
    elif A == 0:
        d_S[(1, 0)] += 0
        d_T[(0, -1)] += 1
    elif B == 0:
        d_S[(1, 0)] += 1
        d_T[(0, -1)] += 0
    else:
        g = gcd(A, B)
        A //= g
        B //= g
        # いずれもマイナスの場合、傾きはプラスになる
        if A < 0 and B < 0:
            A *= -1
            B *= -1
        if A * B > 0:
            d_S[(A, B)] += 1
            d_T[(B, -A)] += 0
        # 片方がマイナスの場合、必ずAがマイナスになるよう揃える
        else:
            if A > B:
                A, B = B, A
            d_S[(-A, B)] += 0
            d_T[(B, A)] += 1

ans = 1
for (si, sj), s_cnt in d_S.items():
    t_cnt = d_T[(sj, -1*si)]
    tmp = 0
    tmp += pow2_mod[s_cnt] - 1 # Sから1匹以上選ぶ組合せ
    tmp += pow2_mod[t_cnt] - 1 # Tから1匹以上選ぶ組合せ
    tmp += 1 # どちらも選ばない組合せ
    ans = (ans * tmp)%MOD

ans -= 1 # 最終的に1匹も選ばない組合せ
ans += zeros # (0, 0)のイワシの数

print(ans%MOD)

Submission status: Runtime Error

Solution code:
import math
import collections
from collections import defaultdict

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

for i in range(N):
    a, b = map(int,input().split())
    if a == 0 and b == 0:
        continue
    elif b == 0:
        iwa,append((1,0))
    elif a == 0:
        iwa.append((0,1))
    elif b > 0:
        c = math.gcd(a,b)
        iwa.append((a/c, b/c))#bは正
    else:
        c = math.gcd(a,b)
        iwa.append((-a/c, -b/c))#bは正
        
S = set(iwa)
I = collections.Counter(iwa)
#print(I)
jdg = defaultdict(int)

ans = 1
for i in S:
    if jdg[i] == 1:
        continue
    elif i == (1,0) or i == (0,1):
        k = I[(1,0)]
        l = I[(0,1)]
        if min(k,l) == 0:
            ans *= pow(2,max(l,k),mod)
        else:
            ans *= (pow(2,l,mod)-1) + (pow(2,k,mod)-1)+1
        jdg[(1,0)] = 1
        jdg[(0,1)] = 1
    else:
        k = I[i]
        a, b = i
        if a < 0:
            l = I[(b,-a)]
            jdg[(b, -a)] = 1
        else:
            l = I[(-b,a)]
            jdg[(-b,a)] = 1
        if min(l,k) == 0:
            ans *= pow(2,max(l,k),mod)
        else:
            ans *= (pow(2,l,mod)-1) + (pow(2,k,mod)-1)+1
        jdg[i] = 1
print(ans-1)

Submission status: Runtime Error

Solution code:
import math
import collections
from collections import defaultdict

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

for i in range(N):
    a, b = map(int,input().split())
    if a == 0 and b == 0:
        continue
    elif b == 0:
        iwa.appned((1,0))
    elif a == 0:
        iwa.append((0,1))
    elif b > 0:
        c = math.gcd(a,b)
        iwa.append((a/c, b/c))#bは正
    else:
        c = math.gcd(a,b)
        iwa.append((-a/c, -b/c))#bは正
        
S = set(iwa)
I = collections.Counter(iwa)
#print(I)
jdg = defaultdict(int)

ans = 1
for i in S:
    if jdg[i] == 1:
        continue
    elif i == (1,0) or i == (0,1):
        k = I[(1,0)]
        l = I[(0,1)]
        if min(k,l) == 0:
            ans *= pow(2,max(l,k),mod)
        else:
            ans *= (pow(2,l,mod)-1) + (pow(2,k,mod)-1)+1
            ans %= mod
        jdg[(1,0)] = 1
        jdg[(0,1)] = 1
    else:
        k = I[i]
        a, b = i
        if a < 0:
            l = I[(b,-a)]
            jdg[(b, -a)] = 1
        else:
            l = I[(-b,a)]
            jdg[(-b,a)] = 1
        if min(l,k) == 0:
            ans *= pow(2,max(l,k),mod)
        else:
            ans *= (pow(2,l,mod)-1) + (pow(2,k,mod)-1)+1
            ans %= mod
        jdg[i] = 1
print(ans-1)