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:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n = II()
    ab = LIR(n)
    d = defaultdict(int)
    d2 = defaultdict(int)
    d3 = defaultdict(int)
    for a, b in ab:
        if a == 0 or b == 0:
            d[0] += 1
        else:
            if a * b > 0:
                x = math.gcd(a, b)
                a //= x
                b //= x
                d[(a , b)] += 1
                d3[(a , b)] = 1
            else:
                x = math.gcd(a, b)
                a //= x
                b //= x
                d2[(abs(b), abs(a))] += 1
                d3[(abs(b), abs(a))] = 1
    ans = 1
    if d[0] != 0:
        ans *= d[0] + 1
    for k in d3.keys():
        ans *= (2 ** d[k] + 2 ** d2[k] - 1)
        ans %= mod
    ans -= 1
    print(ans % mod)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys
from fractions import Fraction
from collections import defaultdict

sys.setrecursionlimit(500000)
def input():
    return sys.stdin.readline()[:-1]

def main():
    N = int(input())

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

    arg = defaultdict(int)
    zero = 0
    for v in vec:
        if v[0] == 0 and v[1] == 0:
            zero += 1
        elif v[1]==0:
            arg[float("inf")] += 1
            arg[0] += 0
        elif v[0]==0:
            arg[0] += 1
            arg[float("inf")] += 0
        else:
            arg[Fraction(v[0],v[1])] += 1
            arg[Fraction(-v[1],v[0])] += 0

    pair = []

    ll = lambda : False

    checked_list = defaultdict(ll)
    for key in arg:
        if not checked_list[key]:
            if key==0:
                pair.append([arg[0],arg[float("inf")]])
                checked_list[float("inf")] = True
            elif key==float("inf"):
                pair.append([arg[0],arg[float("inf")]])
                checked_list[0] = True

            else:
                #print(key)
                pair.append([arg[key],arg[-1/key]])
                #print(pair)
                checked_list[-1/key] = True

    mod = 1000000007

    ans = 1
    """
    for p1,p2 in pair:
        ans *= pow(2,p1,mod) + pow(2,p2,mod) - 1
        ans %= mod
    """
    ans += zero
    ans %= mod

    print(ans-1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys

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

N = ir()
AB = [lr() for _ in range(N)]
graph = [set() for _ in range(N+1)]  # 1-indexed 仲が悪い組み合わせ
#print(AB)
for i in range(1, N+1):
    for j in range(i+1, N+1):
        ai, bi = AB[i-1]
        aj, bj = AB[j-1]
        if ai * aj + bi * bj == 0:
            graph[i].add(j)
#print(graph)
MOD = 1000000007
answer = 0
#used = set()
P = [1] * (N+1)
for i in range(1, N+1):
    P[i] = 2 * P[i-1] % MOD

for i in range(1, N+1):
    #graph[i] -= used
    x = N - i - (len(graph[i]))  # xの中から自由に選ぶ、自分は既に入っているので0もあり
    answer += P[x]
    answer %= MOD
    #print('i', i, answer)
    #used.add(i)

print(answer % MOD)
# np.int64とint型の違いに注意

Submission status: Wrong Answer

Solution code:
import math
from collections import Counter
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(self.power_func(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(self.power_func(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __row__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )

    def power_func(self,a,n,p):
        bi=str(format(n,"b"))#2進表現に
        res=1
        for i in range(len(bi)):
            res=(res*res) %p
            if bi[i]=="1":
                res=(res*a) %p
        return res

    def combination(self,n,r=-1):
        if r==-1:
            r = n
        #nCrの一覧を返す。rの上限も
        if (r<0) or (n<r):
            return 0
        cur = ModInt(1)
        res = []
        res.append(cur)
        for i in range(1,r+1):
            cur *= n + 1 -i
            cur /= i
            res.append(cur)
        return res



#グローバル変数MODを決めてあげてください
MOD = 1000000007

N = int(input())
#双方ノンゼロ...
#Ai*Aj = - Bi* Bj　⇔　Ai/Bi == -Bj/Ai
#絶対値が同じやつら
#片方ゼロ→ノンゼロとは食い合わないがもう片方がゼロならダメ
#両方ゼロ→単騎で選ぶしかない
#ノンゼロ組、片方ゼロ組、両方ゼロ組に分ける
#ノンゼロ*(1 + Aだけゼロ + Bだけゼロ) + 両方ゼロ単騎 
NonZeroPlus = []
NonZeroMinus = []
AZero = 0
BZero = 0
TwoZero = 0
for n in range(N):
    A,B = [int(hoge) for hoge in input().split()]
    if A!=0 and B!=0:
        G = math.gcd(abs(A),abs(B))
        if B < 0:
            G *= -1
            #B//Gが必ず正
        if A//G > 0:
            NonZeroPlus.append((A//G,B//G))
        else:#A//B < 0
            NonZeroMinus.append((B//G,-A//G))
    elif A==B==0:
        TwoZero += 1
    elif A == 0:
        AZero += 1
    else:
        BZero += 1
P = Counter(NonZeroPlus)
M = Counter(NonZeroMinus)
NonZero = ModInt(1)
Daburazu = ModInt(0)
for k in P.keys():
    X,Y = P[k],M[k]
    a = ModInt(2)
    b = ModInt(2)
    if Y:
        NonZero *= (a**X -1) + (b**Y -1) + 1 
    Daburazu += X
for k in M.keys():
    X,Y = P[k],M[k]
    a = ModInt(2)
    if X == 0:
        NonZero *= a**Y
#ノンゼロ組…コレ(0含む)
a = ModInt(2)
b = ModInt(2)
NonZero *= (a**AZero -1) + (b**BZero -1) + 1
NonZero *= TwoZero + 1
print(NonZero - 1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import bisect
import collections
import sys
import math
from fractions import Fraction

sys.setrecursionlimit(1000000)
ACMOD = 1000000007
INF = 1 << 62

MOD = 1000000007  # type: int


def solve(N: int, A: "List[int]", B: "List[int]"):
    ab = collections.defaultdict(lambda: [0, 0])  # [posi][nega]
    zeros = 0
    for i in range(N):
        if A[i] == B[i] == 0:
            zeros += 1
        elif A[i] == 0:
            ab[0][1] += 1
        elif A[i] * B[i] >= 0:
            v = math.gcd(A[i], B[i])
            ab[(abs(B[i]) // v, abs(A[i]) // v)][0] += 1
        else:
            v = math.gcd(A[i], B[i])
            ab[(abs(A[i]) // v, abs(B[i]) // v)][1] += 1

    # check B[i] ==0
    ans = 1
    for x, y in ab.values():
        pattern = 1  # not select
        pattern += 2 ** x - 1
        pattern += 2 ** y - 1
        ans = ans * pattern % MOD
    print((ans - 1) % MOD + zeros)

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, A, B)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
from collections import defaultdict
P = 7 ** 21 + 52
mod = 10 ** 9 + 7
N = int(input())
D = defaultdict(int)
C0 = 0
for i in range(N):
    a, b = map(int, input().split())
    if a == 0 or b == 0:
        C0 += 1
    else:
        x = a * pow(b, P - 2, P) % P
        D[x] += 1
ans = C0 + 1
for x in D:
    y = pow(-x, P - 2, P)
    if y in D and x > y: continue
    ans *= 1 + pow(2, D[x], mod) - 1 + pow(2, (D[y] if y in D else 0), mod) - 1
    ans %= mod
print((ans - 1) % mod)

Submission status: Wrong Answer

Solution code:
from math import gcd
from collections import Counter
n=int(input())

iw=[]
for i in range(n):
    ab=list(map(int, input().split( )))
    iw.append(ab)

for i in range(n):
    ai,bi=iw[i]
    if ai and bi:##互いに素にする
        g=gcd(ai,bi)
        iw[i][0]//=g;iw[i][1]//=g
    else:#どちらか0なら残りを1か0にする
        if ai:#biがゼロでaiが非ゼロ
            iw[i][0]=1
        elif bi:#aiがゼロでbiが非ゼロ
            iw[i][1]=1
    if bi<0:#biは正に設定
        iw[i][0]*=-1;iw[i][1]*=-1
    if bi==0 and ai<0:#biがゼロならaiは正かゼロ
        iw[i][0]*=-1
iw = [tuple(iwi) for iwi in iw]
C=Counter(iw)
ans=1
mod=10**9+7
#print(C)
#ai bi=0,0は別に処理が要る
tmp=0
if (0,0) in C:
    tmp= C.pop((0,0))
for ai,bi in C:
    if ai>0 and C[(ai,bi)]>0:
        if (-bi,ai) in C and C[(-bi,ai)]>0:
            ans*=(pow(2,C[(-bi,ai)],mod)+pow(2,C[(ai,bi)],mod)-1)
            ans%=mod
            C[(-bi,ai)]=-1
        else:
            ans*= pow(2,C[(ai,bi)],mod)
            ans%=mod
    elif ai==0 and C[(ai,bi)]>0:
        if (bi,ai) in C and C[(bi,ai)]>0:
            ans*=(pow(2,C[(bi,ai)],mod)+pow(2,C[(ai,bi)],mod)-1)
            ans%=mod
            C[(bi,ai)]=-1
        else:
            ans*= pow(2,C[(ai,bi)],mod)
            ans%=mod
    elif C[(ai,bi)]>0:
        if (bi,-ai) in C and C[(bi,-ai)]>0:
            ans*=(pow(2,C[(bi,-ai)],mod)+pow(2,C[(ai,bi)],mod)-1)
            ans%=mod
            C[(bi,-ai)]=-1
        else:
            ans*= pow(2,C[(ai,bi)],mod)
            ans%=mod
    
    #print((ai,bi),C[(ai,bi)],ans)
print((ans+tmp-1)%mod)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import math

MOD = 1000000007
n = int(input())


def GCD(a: int, b: int) -> int:
    return a if b == 0 else GCD(b, a % b)


# GCD(-2, 4)

iwasi_cnt = defaultdict(int)
for _ in range(n):
    a, b = map(int, input().split())
    if b < 0:
        a, b = -a, -b
    # iwasi.append((a, b))

    g = GCD(abs(a), b)
    if g == 0:
        # (0, 0)
        iwasi_cnt[(a, b)] += 1
    else:
        iwasi_cnt[(a // g, b // g)] += 1

iwasi_cnt = dict(iwasi_cnt)
# print(iwasi_cnt)
cand = []
for (a, b), v in iwasi_cnt.items():
    if a == 0 and b == 0:
        cand.append((v, ))
    else:
        if (-b, a) in iwasi_cnt:
            m = iwasi_cnt[(-b, a)]
            cand.append((v, m))
        elif (b, -a) not in iwasi_cnt:
            cand.append((v, ))

# print(*cand, sep='\n')
ans = 1
for i in range(len(cand)):
    if len(cand[i]) == 1:
        x = cand[i][0]
        ans *= pow(2, x, MOD)
        ans %= MOD
    else:
        x, y = cand[i]
        ans *= pow(2, x, MOD) + pow(2, y, MOD) - 1
        ans %= MOD

ans -= 1  # 0匹を取り除く
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from itertools import groupby, accumulate, product, permutations, combinations
def solve():
    mod = 10**9+7
    dplus = defaultdict(lambda: 0)
    dminus = defaultdict(lambda: 0)
    N = int(input())
    xzero = 0
    yzero = 0
    for i in range(N):
        x,y = map(int, input().split())
        if x==0:
            xzero += 1
        elif y==0:
            yzero += 1
        elif x/y>0:
            dplus[x/y] += 1
        else:
            dminus[-y/x] += 1
    pattern = 1
    other = N
    pattern = pow(2,xzero,mod)+pow(2,yzero,mod)-1
    other = N-xzero-yzero
    for k,v in dplus.items():
        pattern *= pow(2,dminus[k],mod)+pow(2,v,mod)-1
        other -= dminus[k]+v
    ans = pattern * pow(2,other,mod) - 1
    ans %= mod
    return ans
print(solve())

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from functools import cmp_to_key
n = int(input())
a = [list(map(int,input().split())) for i in range(n)]
mod = 10**9+7
def p2(x):
  return pow(2,x,mod)
n00 = 0
n0x = 0
nx0 = 0
nxy = 0
ls = []
for i in range(n):
  if a[i][0] == a[i][1] == 0:
    n00 += 1
  elif a[i][0] == 0:
    n0x += 1
  elif a[i][1] == 0:
    nx0 += 1
  else:
    nxy += 1
    if a[i][0] < 0 and a[i][1] < 0:
      a[i][0] *= -1
      a[i][1] *= -1
    elif a[i][0] < 0:
      a[i][0] *= -1
      a[i][1] *= -1
    ls.append(a[i])
if len(ls) == 0:
  print((p2(n0x)+p2(nx0)-1+n00-1)%mod)
  exit()
def sorting(x,y):
  if x[0]*y[1]-x[1]*y[0] == 0:
    return 0
  if x[0]*y[1]-x[1]*y[0] > 0:
    return 1
  else:
    return -1
ls.sort(key = cmp_to_key(sorting))
tls = []
t = 1
for i in range(1,nxy):
  if sorting(ls[i],ls[i-1]) == 0:
    t += 1
  else:
    tls.append([t,*ls[i-1]])
    t = 1
tls.append([t,*ls[nxy-1]])
for i in range(len(tls)):
  if tls[i][2] < 0:
    tls = tls[:i]+tls[len(tls)-1:i-1:-1]
    break

l = 0
r = len(tls)-1
banned = []
while l < r:
  la,lb = tls[l][1:]
  ra,rb = tls[r][1:]
  if la*ra + lb*rb == 0:
    banned.append((tls[l][0],tls[r][0]))
    l += 1
    r -= 1
  elif la*ra + lb*rb > 0:
    r -= 1
  else:
    l += 1
sm = sum([banned[i][0]+banned[i][1] for i in range(len(banned))])
ans = p2(n-sm)
for i,j in banned:
  ans = (ans*(p2(i)+p2(j)-1))%mod
k = p2(n0x)+p2(nx0)-1
ans *= k
ans += n00-1
print(ans%mod)

Submission status: Wrong Answer

Solution code:
def examA():
    S = {0:"pon",1:"pon",2:"hon",3:"bon",4:"hon",5:"hon",6:"pon",7:"hon",8:"pon",9:"hon"}
    N = SI()
    ans = S[int(N[-1])]
    print(ans)
    return

def examB():
    K = I()
    S = SI()
    N = len(S)
    if N<=K:
        ans = S
    else:
        ans = S[:K]+"..."
    print(ans)
    return

def examC():
    A, B, H, M = LI()
    a = abs(H*30 - M*5.5)
    deg = min(360-a,a)*math.pi/180
    #print(deg)
    ans = (A**2 + B**2 - 2*A*B*math.cos(deg))**(0.5)
    print(ans)
    return

def examD():

    N, M = LI()
    V = [[]for _ in range(N)]
    for _ in range(M):
        a, b = LI()
        a -= 1; b -= 1
        V[a].append(b)
        V[b].append(a)

    ans = [-1]*N

    def bfs(n, e, fordfs):
        # 点の数、スタートの点、有向グラフ
        W = [-1] * n
        # 各点の状態量、最短距離とか,見たかどうかとか
        W[e] = 0
        que = deque()
        que.append(e)
        while que:
            now = que.popleft()
            nowW = W[now]
            for ne in fordfs[now]:
                if W[ne] == -1:
                    W[ne] = now
                    que.append(ne)
        return W
    ans = bfs(N,0,V)
    for a in ans:
        if a==-1:
            print("No")
            return
    print("Yes")
    for v in ans[1:]:
        print(v+1)
    return

def examE():
    def gcd(x, y):
        if y == 0:
            return x
        while (y != 0):
            x, y = y, x % y
        return x
    N = I()
    D = defaultdict(int)
    D0 = [0,0]
    for i in range(N):
        A = LI()
        if A[0]==0 and A[1]==0:
            continue
        if A[0]==0:
            D0[0] += 1
            continue
        if A[1]==0:
            D0[1] += 1
            continue
        if A[0]<0 and A[1]<0:
            A = [-A[0],-A[1]]
        if A[0]<0:
            k = gcd(-A[0],A[1])
            V = [A[0] // k, A[1] // k]
        elif A[1]<0:
            k = gcd(A[0],-A[1])
            V = [A[0] // k, A[1] // k]
        else:
            k = gcd(A[0],A[1])
            V = [A[0]//k,A[1]//k]
        D[(V[0], V[1])] += 1
    ans = 1
    ans *= (pow(2,D0[0],mod)-1 + pow(2,D0[1],mod)-1 +1)
    ans %= mod
    #print(ans)
    #print(D)
    C = deepcopy(D)
    for (a,b),d in C.items():
        if D[(a,b)]==0:
            continue
        if D[(-b,a)]>0:
            ans *= (pow(2,d,mod)-1 + pow(2,D[(-b,a)])-1 + 1)
            D[(-b,a)] = 0
        elif D[(b,-a)]>0:
            ans *= (pow(2,d,mod)-1 + pow(2,D[(b,-a)])-1 + 1)
            D[(b,-a)] = 0
        else:
            ans *= pow(2,d,mod)
        ans %= mod
        #print(ans,a,b,d)
    ans = (ans+mod-1)%mod
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examE()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Wrong Answer

Solution code:
import sys
from fractions import Fraction
from collections import defaultdict

sys.setrecursionlimit(500000)
def input():
    return sys.stdin.readline()[:-1]

def main():
    N = int(input())

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

    arg = defaultdict(int)
    zero = 0
    for v in vec:
        if v[0] == 0 and v[1] == 0:
            zero += 1
        elif v[1]==0:
            arg[float("inf")] += 1
            arg[0] += 0
        elif v[0]==0:
            arg[0] += 1
            arg[float("inf")] += 0
        else:
            arg[Fraction(v[0],v[1])] += 1
            arg[Fraction(-v[1],v[0])] += 0

    pair = []

    ll = lambda : False

    checked_list = defaultdict(ll)
    for key in arg:
        if not checked_list[key]:
            if key==0:
                pair.append([arg[0],arg[float("inf")]])
                checked_list[float("inf")] = True
            elif key==float("inf"):
                pair.append([arg[0],arg[float("inf")]])
                checked_list[0] = True

            else:
                #print(key)
                pair.append([arg[key],arg[-1/key]])
                #print(pair)
                checked_list[-1/key] = True

    mod = 1000000007

    ans = 1

    for p1,p2 in pair:
        ans *= pow(2,p1,mod) + pow(2,p2,mod) - 1
        ans %= mod

    ans += zero
    ans %= mod

    print(ans-1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
MOD = 1000000007

n = int(input())

# la = []
# lb = []
# for _ in range(n):
#     a, b = map(int, input().split())
#     la.append(a)
#     lb.append(b)


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


def normalize(a, b):
    if a == 0 and b == 0:
        return 0, 0
    elif a != 0 and b == 0:
        return 1, 0
    elif a == 0 and b != 0:
        return 0, 1
    else:
        g = gcd(abs(a), abs(b))
        a //= g
        b //= g
        if a < 0:
            a *= -1
            b *= -1
        return a, b


dv = {}
for _ in range(n):
    a, b = map(int, input().split())
    a, b = normalize(a, b)
    dv[(a, b)] = dv.get((a, b), 0) + 1


counted = {k: False for k in dv.keys()}
nc = 1
for k, v in dv.items():
    if not counted[k]:
        a0, b0 = k
        a1, b1 = normalize(b0, -a0)
        w = dv.get((a1, b1), 0)

        nc *= 1 + (2 ** v - 1) + (2 ** w - 1)
        nc %= MOD

        counted[(a0, b0)] = True
        counted[(a1, b1)] = True

nc -= 1
print(nc)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n = II()
    ab = LIR(n)
    par = [i for i in range(n)]
    d = defaultdict(int)
    d2 = defaultdict(int)
    d3 = defaultdict(int)
    for a, b in ab:
        if a == 0 or b == 0:
            d[0] += 1
            d2[0] += 1
        else:
            if a / b > 0:
                x = math.gcd(a, b)
                a //= x
                b //= x
                d[(a , b)] += 1
                d3[(a , b)] += 1
            else:
                x = math.gcd(a, b)
                a //= x
                b //= x
                d2[(abs(b),abs(a))] += 1
                d3[(abs(b),abs(a))] += 1
    ans = 1
    if d[0] != 0:
        ans *= d[0] + 1
    for k in d3.keys():
        ans *= (2 ** d[k] + 2 ** d2[k] - 1)
        ans %= mod
    ans -= 1
    print(ans % mod)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

Q = 10**9+7

from collections import defaultdict
from math import gcd
def main():
    N = int( input())
    AB = [ tuple( map( int, input().split())) for _ in range(N)]
    d = defaultdict( int)
    for a, b in AB:
        if a == 0 and b == 0:
            d[(0,0)] += 1
            continue
        g = gcd(a, b)
        a //= g
        b //= g
        if a == 0:
            d[(0,1)] += 1
            continue
        if b == 0:
            d[(1,0)] += 1
            continue
        if a < 0:
            a = -a
            b = -b
        d[(a,b)] += 1
    ans = 1
    K = list( d.keys())
    for k in K:
        # print(ans)
        a, b = k
        if a == 0 and b == 0:
            continue
        if a*b == 0:
            if a > 0:
                ans *= (pow(2,d[(1,0)],Q) + pow(2,d[(0,1)],Q) -1)%Q
                ans %= Q
            continue
        if b > 0 and d[(a,b)] > 0 and d[(b,-a)] > 0:
            ans *= (pow(2,d[(a,b)],Q) + pow(2,d[(b,-a)],Q) - 1)%Q
            ans %= Q
            continue
        if b < 0 and d[(a,b)] > 0 and d[(-b,a)] > 0:
            continue
        ans *= pow(2,d[(a,b)],Q)
        ans %= Q
    
    ans -= 1
    ans += d[(0,0)]
    ans %= Q
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
mod = 1000000007
from collections import defaultdict
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

N = int(input())
AB = [list(map(int,input().split())) for _ in range(N)]
d1 = defaultdict(lambda:0)
d2 = defaultdict(lambda:0)
ca = 0
cb = 0
cc = 0
for i in range(N):
    a,b = AB[i]
    if a==0 and b!=0:
        ca += 1
        continue
    elif a!=0 and b==0:
        cb += 1
        continue
    elif a==0 and b==0:
        cc += 1
        continue
    a_ = abs(a)
    b_ = abs(b)
    d = gcd(a,b)
    if d != 0:
        a //= d
        b //= d
    if a < 0:
        a *= -1
        b *= -1
    if b>0:
        d1[(a,b)] += 1
    else:
        d2[(a,b)] += 1
        d1[(-b,a)] += 0

ans = pow(2,ca)+pow(2,cb)-1
for a,b in d1:
    x = d1[(a,b)]
    y = d2[(b,-a)]
    ans *= pow(2,x,mod)+pow(2,y,mod)-1
    ans %= mod
ans -= 1
ans += cc
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys

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

N = ir()
AB = [lr() for _ in range(N)]
graph = [set() for _ in range(N+1)]  # 1-indexed 仲が悪い組み合わせ
#print(AB)
for i in range(1, N+1):
    for j in range(i+1, N+1):
        ai, bi = AB[i-1]
        aj, bj = AB[j-1]
        if ai * aj + bi * bj == 0:
            graph[i].add(j)
print(graph)
MOD = 1000000007
answer = 0
#used = set()
for i in range(1, N+1):
    #graph[i] -= used
    x = N - i - (len(graph[i]))  # xの中から自由に選ぶ、自分は既に入っているので0もあり
    answer += pow(2, x, MOD)
    answer %= MOD
    print('i', i, answer)
    #used.add(i)

print(answer % MOD)
# np.int64とint型の違いに注意

Submission status: Wrong Answer

Solution code:
from fractions import Fraction

N = int(input())

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

from collections import defaultdict

arg = defaultdict(int)
zero = 0
for v in vec:
    if v[0] == 0 and v[1] == 0:
        zero += 1
    elif v[1]==0:
        arg[float("inf")] += 1
        arg[0] += 0
    elif v[0]==0:
        arg[0] += 1
        arg[float("inf")] += 0
    else:
        arg[Fraction(v[0],v[1])] += 1
        arg[Fraction(-v[1],v[0])] += 0

pair = []

ll = lambda : False

checked_list = defaultdict(ll)
for key in arg:
    if not checked_list[key]:
        if key==0:
            pair.append([arg[0],arg[float("inf")]])
            checked_list[float("inf")] = True
        elif key==float("inf"):
            pair.append([arg[0],arg[float("inf")]])
            checked_list[0] = True

        else:
            #print(key)
            pair.append([arg[key],arg[-1/key]])
            #print(pair)
            checked_list[-1/key] = True

mod = 1000000007

ans = 1

for p1,p2 in pair:
    ans *= pow(2,p1,mod) + pow(2,p2,mod) - 1
    ans %= mod

ans += zero
ans %= mod

print(ans-1)

Submission status: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]
def init_dp1(init, N): return [init for _ in range(N)]
def init_dp2(init, N, M): return [[init for _ in range(M)] for _ in range(N)]


def main():
    N = int(input())
    A = read_lists(N)    

    K = {}
    for a in A:
        if a[0] == 0:
            r = "I"
        else:
            r = a[1] / a[0]
        K[r] = K.setdefault(r, 0) + 1

    S = set()
    res = 1
    for k, v in K.items():
        if k in S:
            continue
        S.add(k)

        if k == 0:
            t = "I"
        elif k == "I":
            t = 0
        else:
            t = -1 / k

        if t in K:
            S.add(t)
            v2 = K[t]
            res *= (pow(2, v, mod) + pow(2, v2, mod) - 1)
            res %= mod
        else:
            res *= 2
            res %= mod

    print((res - 1) % mod)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from fractions import Fraction
mod = 1000000007

def solve():
    input = sys.stdin.readline
    N = int(input())
    F = [[int(i) for i in input().split()] for _ in range(N)]
    D = dict()
    for x, y in F:
        if x != 0: tan = Fraction(y, x)
        else: tan = "Inf"
        if tan in D: D[tan] += 1
        else: D[tan] = 1

    ans = 1
    used = set()
    for key in D:
        if key not in used:
            this = D[key]
            used |= {key}
            if key == "Inf":
                op = (0 if 0 not in D else D[0])
                used |= {0}
            elif key == 0: 
                op = (0 if "Inf" not in D else D["Inf"])
                used |= {"Inf"}
            else: 
                nu, de = key.numerator, key.denominator
                op = (0 if Fraction(-de, nu) not in D else D[Fraction(-de, nu)])
                used |= {Fraction(-de, nu)}
            select = (pow(2, this, mod) + pow(2, op, mod) - 1) % mod
            ans *= select
            ans %= mod
    ans = (ans - 1) % mod
    #print(D)
    print(ans)
    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import bisect
import collections
import sys
import math
from fractions import Fraction

sys.setrecursionlimit(1000000)
ACMOD = 1000000007
INF = 1 << 62

MOD = 1000000007  # type: int


def solve(N: int, A: "List[int]", B: "List[int]"):
    ab = collections.defaultdict(lambda: [0, 0])  # [posi][nega]
    zeros = 0
    for i in range(N):
        if A[i] == B[i] == 0:
            zeros += 1
        elif A[i] == 0:
            ab[0][1] += 1
        elif A[i] * B[i] >= 0:
            ab[(abs(B[i]) / abs(A[i]))][0] += 1
        else:
            ab[(abs(A[i]) / abs(B[i]))][1] += 1

    # check B[i] ==0
    ans = 1
    for x, y in ab.values():
        pattern = 1  # not select
        pattern += 2 ** x - 1
        pattern += 2 ** y - 1
        ans = ans * pattern % MOD
    print((ans - 1) % MOD + zeros)

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, A, B)


if __name__ == '__main__':
    main()