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: Wrong Answer

Solution code:
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
    # 入力のbが0の時はaの値を正の1に統一する
    if b == 0 and a == -1:
        a = 1

    # 今bは必ず正
    # aも正，すなわち傾きが正のとき
    if a > 0:
        if (a, b) in d:
            d[(a, b)][0] += 1
        else:
            d[(a, b)] = [1, 0]
    else:
        # aが負，すなわち傾きが負の時
        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)  # 最後の+1はどちらからも選ばなかったパターン
    ans %= MOD
ans -= 1
ans %= MOD
print(ans)

Submission status: Wrong Answer

Solution code:
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
    # 入力のbが0の時はaの値を正の1に統一する
    if b == 0 and a == -1:
        a = 1

    # 今bは必ず正
    # aも正，すなわち傾きが正のとき
    if a > 0:
        if (a, b) in d:
            d[(a, b)][0] += 1
        else:
            d[(a, b)] = [1, 0]
    else:
        # aが負，すなわち傾きが負の時
        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():
    now = pow(2, k, MOD)-1 + pow(2, l, MOD)-1 + 1  # 最後の+1はどちらからも選ばなかったパターン
    ans *= now
    ans %= MOD
ans -= 1
ans %= MOD
print(ans)

Submission status: Wrong Answer

Solution code:
from math import gcd
N=int(input())
mod=10**9+7

zero=0
slope={}
for i in range(N):
    a,b=map(int,input().split())
    if a==0 and b==0:
        zero+=1
        continue
    elif a==0:
        s="0/1"
    elif b==0:
        s="1/0"
    else:
        g=gcd(abs(a),abs(b))
        a//=g
        b//=g
        if b<0:
            a*=-1
            b*=-1
        s=str(a)+"/"+str(b)
    if s in slope:
        slope[s]+=1
    else:
        slope[s]=1

ans=1
rem=[]
for s in slope:
    b2,a2=map(int,s.split("/"))
    if a2!=0 and b2!=0:
        a2*=-1
    if b2<0:
        a2*=-1
        b2*=-1
    s_inv=str(a2)+"/"+str(b2)
    if s_inv in slope:
        rem.append((pow(2,slope[s],mod)-1)*(pow(2,slope[s_inv],mod)-1)%mod)
ans=pow(2,N-zero,mod)-1+zero-(sum(rem)//2)%mod
print(ans%mod)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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:
        C = -B / A
        ab.append(-B / A)

c = Counter(ab)

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

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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
        elif 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: Wrong Answer

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
        else:
            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
                
        else:
            t=(-1)/k
            if t in vec:
                banpair.append((v,vec[t]))
                seen.add(t)
                continue
        #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: Wrong Answer

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
        else:
            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
                
        else:
            t=(-1)/k
            if t in vec:
                banpair.append((v,vec[t]))
                seen.add(t)
                continue
        #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=(pow(2,ori,MOD)-1)
    print((ans1+ans2)%MOD)   
#%%submit!
resolve()

Submission status: Wrong Answer

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
        else:
            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
                
        else:
            t=(-1)/k
            if t in vec:
                banpair.append((v,vec[t]))
                seen.add(t)
                continue
        #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=(pow(2,ori,MOD)-1)
    print(ans1+ans2)    
#%%submit!
resolve()

Submission status: Wrong Answer

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
        else:
            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
                
        else:
            t=(-1)/k
            if t in vec:
                banpair.append((v,vec[t]))
                seen.add(t)
                continue
        #print(k,v,"reg")
        reg+=v

    #print(banpair)
    lenb=len(banpair)
    stack=[(0,1)]
    bans=0
    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=(pow(2,ori,MOD)-1)
    print(ans1+ans2)    
#%%submit!
resolve()

Submission status: Wrong Answer

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())
    N = int(input())
    AB = (map(int, input().split()) for _ in range(N))

    d = defaultdict(int)
    n_zeros = 0

    for a, b in AB:
        if a == 0 and b == 0:
            n_zeros += 1
            continue

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

        if a == 0:
            c = 1
        elif b == 0:
            c = -1
        elif a * b > 0:
            c = abs(a) + abs(b) * 1j
        else:  # a * b < 0 or a == 0
            c = - abs(b) - abs(a) * 1j

        d[c] += 1

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

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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():
    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
        else:
            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
                
        else:
            t=(-1)/k
            if t in vec:
                banpair.append((v,vec[t]))
                seen.add(t)
                continue
        #print(k,v,"reg")
        reg+=v

    #print(banpair)
    lenb=len(banpair)
    stack=[(0,1)]
    bans=0
    while(stack!=[]):
        p,q=stack.pop()
        if p==lenb:
            bans+=q
            continue
        for i in range(2):
            stack.append((p+1,q*(2**banpair[p][i]-1)))
        stack.append((p+1,q*1))
    #print(bans,reg)
    #print(N-reg-bans)
    print(2**ori-1+(2**(reg))*(bans)-1)    
#%%submit!
resolve()

Submission status: Wrong Answer

Solution code:
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
    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)
        ans -= p
        ans %= MOD
    if 1 < cnt[0]:
        p = 0
        st = set()
        L = 1
        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()

Submission status: Wrong Answer

Solution code:
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
    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)
        ans -= p
        ans %= MOD
    if 1 < cnt[0]:
        p = 0
        st = set()
        L = 1
        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
            st.add(v)
            st.add(u)
        p %= MOD
        ans -= p
        ans %= MOD
    print(ans%MOD)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import math

n=int(input())

def gcd(x,y):
    if x>y: x,y=y,x
    while x:
        x,y=y%x,x
    return y

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=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+=1
        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)

Submission status: Wrong Answer

Solution code:
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+=1
        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)

Submission status: Wrong Answer

Solution code:
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+=1
        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)

Submission status: Wrong Answer

Solution code:
import math
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
            x = int(x)
            y = int(y)
            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
        #print(mp)    
    #print(mp)
    ans = 1
    for (a, b) in mp.keys():
        now = 1
        #now += np.power(2, mp[a, b][0]) -1 
        #now += np.power(2, mp[a, b][1]) -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()

Submission status: Wrong Answer

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

#a,bの最大公約数
def gcd(a,b):
    if(b==0):
        return a
    else:
        return gcd(b, a%b)

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


ab_p={}
ab_m={}
ab_zeros=0
for i in range(n):
    a,b=map(int,input().split())
    if(a==0 and b==0):
        ab_zeros+=1
    elif(a==0):
        ab_p[(0,-1)]=ab_p.get((0,-1),0)+1
    elif(b==0):
        ab_m[(1,0)]=ab_m.get((1,0),0)+1
    else:
        ab_gcd=gcd(a,b)
        a//=ab_gcd
        b//=ab_gcd
        if(a<0):
            a*=-1
            b*=-1

        if(a*b>0):
            ab_m[(a,b)]=ab_m.get((a,b),0)+1
        else:
            ab_p[(a,b)]=ab_p.get((a,b),0)+1

ans=1
for (ab_i,ab_j),ab_v in ab_m.items():
    t_v = ab_p.get((ab_j,-1*ab_i),0)
    ansi=0
    ansi+=sq_mod[ab_v]-1
    ansi+=sq_mod[t_v]-1
    ansi+=1
    ans=(ans*ansi)%MOD

ans-=1
ans+=ab_zeros

print(ans%MOD)