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:
import math
from collections import Counter

mod = 10**9+7
n = int(input())
c = Counter()
cc = Counter()

iwashi = []
for _ in range(n):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        c[-1] += 1
        continue
    rad = round(math.degrees(math.atan2(a, b)), 20)
    if rad - 180 == 0:
        rad = 0
    if rad < 0:
        rad += 180
    iwashi.append([a, b, rad])
    c[rad] += 1
    cc[rad] += 1


l = []

for r in cc.keys():
    if r == -1:
        continue
    if 0 <= r < 90:
        ra = c[r]
        rb = c[r+90]
        if ra >= 0 and rb >= 0:
            l.append([ra, rb])
        c[r] -= 10**9
        c[r+90] -= 10**9
    else:
        ra = c[r-90]
        rb = c[r]
        if ra >= 0 and rb >= 0:
            l.append([ra, rb])
        c[r-90] -= 10**9
        c[r] -= 10**9

ans = 1

for a, b in l:
    ans *= pow(2, a, mod)-1 + pow(2, b, mod)-1 + 1
    ans %= mod

ans = (ans-1) + c[-1]
ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
import collections
n=int(input())
A=[]
AA=[]
B=[]
C=[]
X=[]
mod=10**9+7
for i in range(n):
  a,b=map(int,input().split())
  if a<0:
    a=a*-1
    b=b*-1
  if a*b>0:
    A.append(b*pow(a,mod-2,mod)%mod)
  elif a*b<0:
    AA.append(a*pow((-b),mod-2,mod)%mod)
  else:
    if a==0 and b==0:
      X.append(i)
    elif a==0:
      B.append(i)
    else:
      C.append(i)
D=collections.Counter(A)
DD=collections.Counter(AA)
E=set(list(D)+list(DD))
a=1
for i in E:
  a=(a*(2**D[i]+2**DD[i]-1))%mod
a=(a*(2**len(B)+2**len(C)-1)-1)%mod
print((a+len(X))%mod)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

#通分
def f(a,b):
    f = math.gcd(a,b)
    return a//f, b//f

N = I()
A,B = LIR(N,2)

beki = [1]*(N+1)
for i in range(1,N+1):
    beki[i] = beki[i-1]*2
    beki[i] %= mod


dplus = defaultdict(int)
dminus = defaultdict(int)
dminus2 = defaultdict(int)
zero = 0
for i in range(N):
    if A[i] == 0 or B[i] == 0:
        zero += 1
    else:
        if A[i]*B[i] > 0:
            a,b = f(abs(A[i]),abs(B[i]))
            dplus[(a,b)] += 1
        else:
            a,b = f(abs(A[i]),abs(B[i]))
            dminus[(b,a)] += 1
            dminus2[(b,a)] += 1

ans = zero+1
count = 0

for k in dplus.keys():
    if dminus[k]:
        temp = beki[dplus[k]] + beki[dminus[k]] - 1
        ans *= temp
        ans %= mod
    else:
        count += dplus[k]

for k in dminus2.keys():
    if dplus[k]:
        continue
    else:
        count += dminus[k]

ans *= beki[count]
ans -= 1
ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline
from functools import cmp_to_key
 
def main():
    n = int(readline())
    x, y  = [], []
    add = 0
    for i in range(n):
        a, b = map(int, readline().split())
        if a == 0 and b == 0:
            add += 1
            continue
        x.append(a)
        y.append(b)

    p = []
    index = 0
    for a, b in zip(x, y):
        cx = a
        cy = b
        if (-cx, -cy) > (cx, cy):
            cx = -cx
            cy = -cy
        p.append((cx, cy, 1, index))
        
        cx = b
        cy = -a
        if (-cx, -cy) > (cx, cy):
            cx = -cx
            cy = -cy
        p.append((cx, cy, 2, index))

        index += 1

    def compare(p1, p2):
        x1, y1, _, __ = p1
        x2, y2, _, __ = p2
        return x1 * y2 - x2 * y1

    p = sorted(p, key=cmp_to_key(compare))
    #print p

    mod = 1000000007

    def GetValue(group):
        min1 = 10 ** 10
        min2 = 10 ** 10
        pow1 = 1
        pow2 = 1
        for g in group:
            _, __, t, i = g
            if t == 1:
                min1 = min(min1, i)
                pow1 = pow1 * 2 % mod
            else:
                min2 = min(min2, i)
                pow2 = pow2 * 2 % mod
        result = (pow1 + pow2 - 1 + mod) % mod
        if min1 > min2:
            result = 1
        #print group, result
        return result
        

    group = []
    result = 1
    for i in range(len(p) + 1):
        if i == len(p) or (len(group) > 0 and compare(group[-1], p[i]) != 0):
            result = result * GetValue(group) % mod 
            group = []
        if i < len(p):
            group.append(p[i])

    result -= 1

    print(result + add)



 
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
input = lambda: sys.stdin.readline().rstrip()
MOD = 10**9+7
MAX = 2*(10**5)+1
sqr = [1 for _ in range(MAX)]
for i in range(1, MAX):
    sqr[i] = sqr[i-1] * 2
    sqr[i] %= MOD

class FLT:
    def __init__(self, mod=10**9+7):
        self.mod = mod

    def rep_sqr(self, base, k):
        ans = 1
        while k > 0:
            if k & 1:
                ans = ans * base % self.mod
            base = base * base % self.mod
            k >>= 1
        return ans

    def inv(self, a):
        """ 逆元を取る """
        return self.rep_sqr(a, self.mod-2)

n = int(input())
d = defaultdict(lambda: 0)
ans = 1
flt = FLT()
cnt_0 = 0
for i in range(n):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        cnt_0 += 1
        continue

    key1 = format(- b / a, '.14f').rstrip('0').rstrip('.') if a != 0 else "nothing"
    cnt = d[key1]
    if cnt <= 0:
        ans *= 2
    else:
        ans *= flt.inv(sqr[cnt])
        ans *= (sqr[cnt] + 1)
    ans %= MOD
    key2 = format(a / b, '.14f').rstrip('0').rstrip('.') if b != 0 else "something"
    d[key2] += 1
# print(d)
print(ans-1+cnt_0)

Submission status: Wrong Answer

Solution code:
from math import degrees, atan2
from collections import defaultdict

MOD = 10**9+7
N = int(input())
# y, xの順に渡すので注意
# print(math.degrees(math.atan2(3**(1/2), 1)))

points = [list(map(int, input().split())) for _ in range(N)]
tmp = defaultdict(int)
for i in range(N):
    a, b = points[i]  # bをy座標, aをx座標と考える
    tmp[degrees(atan2(b, a)) % 90] += 1
# 90になる
# 絶対値にしてmod90で同じものがあるかどうか
# 数えることができている
ans = 1
for v in tmp.values():
    ans *= (v+1)
    ans %= MOD
print(ans-1)

Submission status: Wrong Answer

Solution code:
n=int(input())
ablist=[]
slist=[]
zeros=[0,0,0]

for i in range(n):
    a, b = map(int,input().split())
    if a==0:
        if b==0:
            zeros[2]+=1
        else:
            zeros[1]+=1
    else:
        if b==0:
            zeros[0]+=1
        else:
            if a*b>0:
                slist.append([a/b, 1])
            else:
                slist.append([b/(-a), -1])
                #slist.append([abs(a/b), int(abs(a*b)/(a*b))])

slist=sorted(slist)
#print(slist)

zerok=2**(zeros[0]) + 2**(zeros[1]) - 1
#print(zerok)

mae=[0, 0]
onaji=[1, 0]

answer=1
#print(slist)

rev=0
swit=0
#print(slist)

for sl in slist:
    swit=0
    if sl[0]==mae[0]:
        if sl[1]==mae[1]:
            if rev==0:
                onaji[0]+=1
            else:
                onaji[1]+=1
        else:
            onaji[1]+=1
            rev=1
        
    else:
        if mae!=[0, 0]:
            answer*=(2**onaji[0]+2**onaji[1]-1)
            answer%=1000000007
            onaji=[1, 0]
            rev=0
            swit=1
    mae=sl
    #print(answer)

if len(slist)>0:
    answer*=(2**onaji[0]+2**onaji[1]-1)
    answer%=1000000007

#print(answer)

answer*=zerok
answer+=zeros[2]

print((answer-1)%1000000007)

Submission status: Wrong Answer

Solution code:
MOD = 10**9+7
class mint:
    def __init__(self, x):
        self.x = x % MOD if isinstance(x, int) else int(x) % MOD
    def __str__(self):
        return str(self.x)
    __repr__ = __str__
    def __iadd__(self, other):
        self.x += other.x if isinstance(other, mint) else other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __isub__(self, other):
        self.x += MOD-other.x if isinstance(other, mint) else MOD-other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __imul__(self, other):
        self.x *= other.x if isinstance(other, mint) else other
        self.x %= MOD
        return self
    def __imod__(self, other):
        self.x %= other.x if isinstance(other, mint) else other
        self.x %= MOD
        return self
    def __add__(self, other):
        return (
            mint(self.x + other.x) if isinstance(other, mint) else
            mint(self.x + other)
        )
    def __sub__(self, other):
        return (
            mint(self.x - other.x) if isinstance(other, mint) else
            mint(self.x - other)
        )
    def __mul__(self, other):
        return (
            mint(self.x * other.x) if isinstance(other, mint) else
            mint(self.x * other)
        )
    def __mod__(self, other):
        return (
            mint(self.x % other.x) if isinstance(other, mint) else
            mint(self.x % other)
        )
    def __truediv__(self, other):
        return (
            mint(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(self.x * pow(other, MOD - 2, MOD))
        )
    def __pow__(self, other):
        return (
            mint(pow(self.x, other.x, MOD)) if isinstance(other, mint) else
            mint(pow(self.x, other, MOD))
        )
    __radd__ = __add__
    def __rsub__(self, other):
        return (
            mint(other.x - self.x) if isinstance(other, mint) else
            mint(other - self.x)
        )
    __rmul__ = __mul__
    def __rmod__(self, other):
        return (
            mint(other.x % self.x) if isinstance(other, mint) else
            mint(other % self.x)
        )
    def __rtruediv__(self, other):
        return (
            mint(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(other * pow(self.x, MOD - 2, MOD))
        )
    def __rpow__(self, other):
        return (
            mint(pow(other.x, self.x, MOD)) if isinstance(other, mint) else
            mint(pow(other, self.x, MOD))
        )
import math

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

d=dict()
for i in range(n):
    g=math.gcd(a[i],b[i])
    if g>1:
        a[i]//=g
        b[i]//=g
    if b[i]<0:
        a[i]*=-1
        b[i]*=-1
    if a[i]==0 or b[i]==0:
        a[i]=0
        b[i]=0
    try:
        d[(a[i],b[i])]+=1
    except:
        d[(a[i],b[i])]=1
ok=n
ls=[]
for ap,bp in d.keys():
    try:
        now = d[ap,bp]
    except:
        continue
    try:
        anow = ap
        bnow = bp
        if ap<0:
            anow*=-1
            bnow*=-1
        if ap!=0:
            ok = ok-now-d[(-bnow,anow)]
            ng = d[(-bnow,anow)]
            ls.append(mint(pow(2,now,MOD))+mint(pow(2,ng,MOD)-1))
            d[ap,bp]=0
            d[(-bnow,anow)]=0
        else:
            ok = ok - now
            ng = now
            ls.append(mint(now+1))
            d[ap,bp]=0
    except:
        pass

ans=mint(pow(2,ok,MOD))
for i in ls:
    ans*= i

ans-=mint(1)

print(ans)

Submission status: Wrong Answer

Solution code:
import collections
n=int(input())
A=[]
AA=[]
B=[]
C=[]
X=[]
mod=10**9+7
for i in range(n):
  a,b=map(int,input().split())
  if a<0:
    a=a*-1
    b=b*-1
  if a*b>0:
    A.append(b*pow(a,mod-2,mod)%mod)
  elif a*b<0:
    AA.append(a*pow((-b),mod-2,mod)%mod)
  else:
    if a==0 and b==0:
      X.append(i)
    elif a==0:
      B.append(i)
    else:
      C.append(i)
D=collections.Counter(A)
DD=collections.Counter(AA)
E=set(list(D)+list(DD))
a=1
for i in E:
  a=(a*(2**D[i]+2**DD[i]-1))%mod
a=(a*(2**len(B)+2**len(C)-1)-1+len(X))%mod
print(a)

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log,gcd #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
#mint
class ModInt:
    def __init__(self, x):
        self.x = x % mod
    
    def __str__(self):
        return str(self.x)
    
    __repr__ = __str__

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

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

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

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

    __rmul__ = __mul__

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

    def __pow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(self.x, other.x, mod))
        else:
            return ModInt(pow(self.x, other, mod))
            

    def __rpow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(other.x, self.x, mod))
        else:
            return ModInt(pow(other, self.x, mod))



def main():
    N=I()
    A,B=[],[]
    for i in range(N):
        a,b = MI()
        A.append(a)
        B.append(b)
    both_zero_cnt = 0
    num_of_group = defaultdict(int) ##既約分数にしてあげて、(分子,分母)がkeyで、負なら分子が負になる他は正
    for i in range(N):
        a,b = A[i], B[i]
        if(a==b==0):
            both_zero_cnt+=1
            continue
        elif(a==0):
            num_of_group[-inf,inf] += 1
        elif(b==0):
            num_of_group[inf,inf] += 1
        else:
            if(a*b<0):
                a,b=abs(a),abs(b)
                g = gcd(a,b)
                a//=g
                b//=g
                num_of_group[(-b,a)] += 1
                num_of_group[(b,a)] += 0
            else:
                a,b=abs(a),abs(b)
                g = gcd(a,b)
                a//=g
                b//=g
                num_of_group[(a,b)] += 1
    # print(num_of_group.items())
    if(both_zero_cnt==N):
        print(N)
        return
    ##solve
    ans = ModInt(1)
    two_pow = [1]
    for i in range(N):
        two_pow.append((2*two_pow[-1])%mod)
    # print(two_pow,"#######")
    for (a,b),cnt1 in num_of_group.items():
        if(a<0):
            continue
        tmp = two_pow[cnt1]
        # print((a,b),cnt1)
        # print(tmp)

        if (-a,b) in num_of_group:
            cnt2 = num_of_group[-a,b]
            tmp += two_pow[cnt2]
            tmp-=1
        if(tmp):
            ans *= tmp
    ans -= 1 ##全部選ばない
    ans += both_zero_cnt
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from itertools import combinations_with_replacement
def room1(room):
    C=0
    p = list(combinations_with_replacement(room, 2))
    for i in p:
        if i[0][0]*i[1][0] + i[1][1]*i[0][1] != 0:
            C += 1
            
    return C

t = int(input())
room = []

for i in range(t):
    p, q = map(int, input().split())
    m = [p, q]

    room.append(m)


print(room1(room))

Submission status: Wrong Answer

Solution code:
from fractions import Fraction
import os
from collections import Counter

import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N = int(sys.stdin.buffer.readline())
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N)]

zeros_cnt = 0
A = []
B = []
for a, b in AB:
    if a == 0 or b == 0:
        zeros_cnt += 1
    else:
        A.append(a)
        B.append(b)

ab = [Fraction(a, b) for a, b in zip(A, B)]
ba = [Fraction(b, a) for a, b in zip(A, B)]

counts = Counter(ba)
ans = 1
nandemo = 0
for f, cnt in Counter(ab).items():
    if counts[-f] == 0:
        nandemo += cnt
    else:
        if f > 0:
            ans *= pow(2, cnt, MOD) + pow(2, counts[-f], MOD) - 1
            ans %= MOD
ans *= zeros_cnt + 1
ans %= MOD
ans *= pow(2, nandemo, MOD)
ans -= 1
ans %= MOD
print(ans)

Submission status: Wrong Answer

Solution code:
import math
from collections import Counter

N = int(input())
A_B = []
mod = 1000000007
for _ in range(N):
    A, B = map(int, input().split())
    if (A == 0) and (B == 0):
        A_B.append((A, B))
    elif A == 0:
        A_B.append((0, -1))
    elif B == 0:
        A_B.append((1, 0))
    else:
        if A < 0:
            A = -A
            B = -B
        C = math.gcd(abs(A), abs(B))
        A_B.append((A // C, B // C))

A_B_C = Counter(A_B)


ans = 1
Done = set([])
for key, value in A_B_C.items():
    if key in Done:
        continue
    keya, keyb = key
    a = 0
    if keyb < 0:
        keya = -keya
        keyb = -keyb
    if (keyb, -keya) not in A_B_C:
        a = pow(2, value, mod)
    else:
        a = (pow(2, value, mod) - 1) + (pow(2, A_B_C[(keyb, -keya)], mod) - 1) + 1
        Done.add((keyb, -keya))
    ans *= a
    ans %= mod
    Done.add(key)

print((ans - 1) % mod)

Submission status: Wrong Answer

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

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

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

from collections import Counter
from fractions import Fraction
C=Counter()

for a,b in S:
    if a==0 and b==0:
        continue
    if b!=0:
        C[Fraction(a,b)]+=1
    else:
        C[float("inf")]+=1
    
ANS=0

#print(C)
P=[]

for x in list(C.keys()):
    if x!=float("inf") and x!=Fraction(0,1):
        n=x.numerator
        d=x.denominator

        P.append((C[x],C[Fraction(-d,n)]))
        C[x]=0
        C[Fraction(-d,n)]=0
    else:
        P.append((C[float("inf")],C[(0,1)]))
        C[float("inf")]=0
        C[(0,1)]=0

ANS=1
for x,y in P:
    if x==0 and y==0:
        continue
    else:
        #print(x,y,pow(2,x,mod)+pow(2,y,mod)-1)
        ANS=ANS*(pow(2,x,mod)+pow(2,y,mod)-1)%mod

print((ANS-1)%mod)

Submission status: Wrong Answer

Solution code:
import math
from collections import Counter

mod = 10**9+7
n = int(input())
c = Counter()
cc = Counter()

iwashi = []
for _ in range(n):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        c[-1] += 1
        continue
    rad = round(math.degrees(math.atan2(a, b)), 10)
    if rad - 180 == 0:
        rad = 0
    if rad < 0:
        rad += 180
    iwashi.append([a, b, rad])
    c[rad] += 1
    cc[rad] += 1


l = []

for r in cc.keys():
    if r == -1:
        continue
    if 0 <= r < 90:
        ra = c[r]
        rb = c[r+90]
        if ra >= 0 and rb >= 0:
            l.append([ra, rb])
        c[r] -= 10**9
        c[r+90] -= 10**9
    else:
        ra = c[r-90]
        rb = c[r]
        if ra >= 0 and rb >= 0:
            l.append([ra, rb])
        c[r-90] -= 10**9
        c[r] -= 10**9

ans = 1

for a, b in l:
    ans *= pow(2, a, mod)-1 + pow(2, b, mod)-1 + 1
    ans %= mod

ans = (ans-1) + c[-1]
ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
import math,sys
input = sys.stdin.readline
from collections import defaultdict
n = int(input())
MOD = 1000000007
d = defaultdict(int)
l,r = 0,0
for i in range(n):
  a,b = map(int,input().split())
  if a == b == 0:
    continue
  elif a == 0 or b == 0:
    if a == 0:
      l += 1
    else:
      r += 1
  else:
    g = math.gcd(a,b)
    a,b = a//g,b//g
    if a<0:
      a,b = -a,-b
    d[str(a)+':'+str(b)] += 1
c = 1
for i in d.keys():
  if d[i] != 0:
    cur = pow(2,d[i],MOD)
    if '-' in i:
      ind = i.index(':')
      ci = i[ind+2:] + ':' + i[:ind]
    else:
      ind = i.index(':')
      ci = i[ind+1:] + ':-' + i[:ind]
    if ci in d.keys():
      cur += pow(2,d[ci],MOD)-1
      d[ci] = 0
    c = (c*cur)%MOD
c = (c*(pow(2,l,MOD)+pow(2,r,MOD)-1)-1)%MOD
print(c)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from math import gcd


def normal(x, y):
    if x == 0:
        return (0, 1)
    elif y == 0:
        return (1, 0)
    g = gcd(x, y)
    x, y = x // g, y // g
    if x < 0:
        x, y = -x, -y
    return (x, y)


def orthogonal(T):
    if T[0] == 0:
        return (1, 0)
    elif T[1] == 0:
        return (0, 1)
    if T[1] > 0:
        return (T[1], -T[0])
    else:
        return (-T[1], T[0])


N = int(input())
C = defaultdict(int)
for i in range(N):
    Ai, Bi = map(int, input().split())
    if Ai == Bi == 0:
        continue
    n = normal(Ai, Bi)
    C[n] += 1

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

ans = 1
calc = set()
for n, c in C.items():
    if n in calc:
        continue
    a = B[c]
    calc.add(n)
    no = orthogonal(n)
    if no in C:
        co = C[no]
        a += B[co] - 1
        calc.add(no)
    ans *= a
    ans %= MOD
print(ans - 1)

Submission status: Wrong Answer

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

from fractions import gcd


MOD = 10**9+7
N = int(input())
F = []
zero_v = 0
inf = 0
zero = 0
for _ in range(N):
  x,y = map(int,input().split())
  if x==0 and y==0:
    zero_v += 1
  elif x==0:
    inf += 1
  elif y==0:
    zero += 1
  else:
    #G = gcd(abs(x),abs(y))
    F.append((x,y))

all_keys = set()

for x,y in F:
  if x*y >0:
    if x>0:
      all_keys.add((x,y))
    else:
      all_keys.add((-x,-y))
  x,y = -y,x
  if x*y >0:
    if x>0:
      all_keys.add((x,y))
    else:
      all_keys.add((-x,-y))

all_dic = {k:[0,0] for k in all_keys}

for x,y in F:
  if x*y > 0:
    if x>0:
      all_dic[(x,y)][0] += 1
    else:
      all_dic[(-x,-y)][0] += 1
  else:
    if x>0:
      all_dic[(-y,x)][1] += 1
    else:
      all_dic[(y,-x)][1] += 1

ans = (pow(2,inf,MOD)) + (pow(2,zero,MOD))-1
ans %= MOD

for k in all_keys:
  P,N = all_dic[k]
  ans *= (pow(2,P,MOD)) + (pow(2,N,MOD))-1
  ans %= MOD


ans += zero_v-1

print(ans%MOD)

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

from math import gcd
from collections import defaultdict


n = readint()

mod = 1000000007

d = defaultdict(int)

for i in range(n):
    a,b = readints()
    g = gcd(a,b)
    if g!=0:
        a//=g
        b//=g
    if a<0:
        a*=-1
        b*=-1
    elif a==0 and b<0:
        b*=-1
    d[(a,b)]+=1

ans = 1
k = tuple(d.keys())
for x in k:
    if x[1]>0:
        ans *= pow(2,d[x],mod)+pow(2,d[(x[1],-x[0])],mod)-1
    elif x[1]<0:
        if d[(-x[1],x[0])]==0:
            ans *= pow(2, d[x], mod)
    else:
        if x[0]==0:
            ans *= d[x]+1
        else:
            if d[(-x[1], x[0])] == 0:
                ans *= pow(2, d[x], mod)

    ans %= mod

print(ans-1)

Submission status: Wrong Answer

Solution code:
mod = 1000000007
N = int(input())
p_p = []
p_m = []
m_p = []
m_m = []
z_z = []
z_p = []
z_m = []
p_z = []
m_z = []
if N == 1:
    print(1)

else:
    for _ in range(N):
        tmp = list(map(int, input().split()))
        if tmp[0] > 0:
            if tmp[1] > 0:
                p_p.append(tmp)
            elif tmp[0] == 0:
                p_z.append(tmp)
            else:
                p_m.append(tmp)
        if tmp[0] == 0:
            if tmp[1] > 0:
                z_p.append(tmp)
            elif tmp[0] == 0:
                z_z.append(tmp)
            else:
                z_m.append(tmp)
        if tmp[0] < 0:
            if tmp[1] > 0:
                m_p.append(tmp)
            elif tmp[0] == 0:
                m_z.append(tmp)
            else:
                m_m.append(tmp)

    counter = 0
    counter += len(z_z) * (N - len(z_z))
    counter = counter % mod
    counter += (len(z_p) + len(z_m)) * (len(p_z) + len(m_z))
    counter = counter % mod
    for a in p_p:
        for b in (p_m + m_p):
            if a[0]*b[0] + a[1] * b[1] == 0:
                counter += 1
    counter = counter % mod
    for a in m_m:
        for b in (p_m + m_p):
            if a[0]*b[0] + a[1] * b[1] == 0:
                counter += 1

    counter = counter % mod
    all_num = (2**N-1) % mod
    answer =(all_num - counter* (2 ** (N-2))) % mod

    print(answer)

Submission status: Wrong Answer

Solution code:
n = int(input())
zeros = 0
m = {}

mod = 10**9 + 7

def pmod(a, x) :
	if x == 0 :
		return 1
	sq = pmod(a,x//2)
	sq = (sq * sq) % mod
	if x%2 == 0 :
		return sq
	return (sq * a) % mod

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

for _ in range(n):
	a,b = map(int, input().split())
	if a == 0 and b == 0:
		zeros += 1
		continue
	d = gcd(abs(a), abs(b))
	a, b = a/d, b/d;
	if a < 0 :
		a, b = -a, -b
	if a == 0 and b < 0 :
		b = -b
	if (a,b) in m :
		m[(a,b)] += 1;
	else :
		m[(a,b)] = 1

ans = 1
for u in m:
	ile = m[u]
	a, b = u[0], u[1]
	m[u] = 0
	ile2 = 0
	inv = (b, -a)
	if (b < 0) :
		inv = (-b, a)
	if b == 0 and a > 0 :
		inv = (0, 1)
	if inv in m:
		ile2 = m[inv]
		m[inv] = 0
	ans = (ans * (pmod(2, ile) + pmod(2, ile2) - 1)) % mod;

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

Submission status: Wrong Answer

Solution code:
import math
MOD = 10**9 + 7


def pow_k(x, n):
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2

    return K * x

n = int(input())

a_b_d = {}
# b_a_d = {}

zero_cnt = 0

for i in range(n):
    a, b = map(int, input().split()) 
    if a==0 or b==0:
        zero_cnt += 1
    else:
        gcd_ab = math.gcd(a,b)
        a = a//gcd_ab
        b = b//gcd_ab
        if a > 0 and b < 0:
            a *= -1
            b *= -1
        elif a < 0 and b < 0:
            a *= -1
            b *=-1
        a_b_d.setdefault((a,b),0)
        a_b_d[(a,b)] += 1

done_list = []
pair_cnt = []
uniq_cnt = 0
for k,v in a_b_d.items():
    comp_pair1 = (-k[1], k[0])
    comp_pair2 = (k[1], -k[0])
    if k in done_list:
        continue
    if comp_pair1 in a_b_d:
        # print(k, comp_pair)
        done_list.append(comp_pair1)
        pair_cnt.append((v,a_b_d[comp_pair1]))
    elif comp_pair2 in a_b_d:
        # print(k, comp_pair)
        done_list.append(comp_pair2)
        pair_cnt.append((v,a_b_d[comp_pair2]))
    else:
        uniq_cnt += 1


ans = pow_k(2,uniq_cnt) % MOD
for pair in pair_cnt:
    ans *= (pow_k(2,pair[0]) + pow_k(2,pair[1]) -1 )
    ans%=MOD

ans *= (zero_cnt+1)
ans -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
M = 1000000007

from fractions import Fraction
from bisect import bisect_left

N = int(input())

ab_zero_count = 0
a_zero_count = 0
b_zero_count = 0

fish_list = []
for _ in range(N):
	a, b = map(int, input().split())
	if a == 0 and b == 0:
		ab_zero_count += 1
	elif a == 0:
		a_zero_count += 1
	elif b == 0:
		b_zero_count += 1
	else:
		fish_list.append(Fraction(a, b))

#print(fish_list)

fish_table = {}
for f in fish_list:
	if f in fish_table:
		fish_table[f] += 1
	else:
		fish_table[f] = 1

fish_count_list = list(fish_table.items())
fish_count_list.sort()
fish_count_only_list = [f for f, c in fish_count_list]

#print(fish_count_list)

singles = 0
pair_list = []
checked = [False] * N

for i, (f, c) in enumerate(fish_count_list):
	x = -1 / f
	j = bisect_left(fish_count_only_list, x)
	if j != len(fish_count_only_list) and fish_count_only_list[j] == x:
		if checked[j] == False:
			f2, c2 = fish_count_list[j]
			pair_list.append((c, c2))
			checked[i] = True
	else:
		singles += 1

count = pow(2, singles, M)

if a_zero_count > 0 and b_zero_count > 0:
	pair_list.append((a_zero_count, b_zero_count))
else:
	singles += a_zero_count + b_zero_count

#print(singles, pair_list)

for c1, c2 in pair_list:
	count = (count * (pow(2, c1, M) + pow(2, c2, M) - 1)) % M

count += ab_zero_count
count -= 1

print(count % M)

Submission status: Wrong Answer

Solution code:
import math
from collections import Counter

N = int(input())
A_B = []
mod = 1000000007
for _ in range(N):
    A, B = map(int, input().split())
    if (A == 0) and (B == 0):
        A_B.append((A, B))
    elif A == 0:
        A_B.append((0, 1))
    elif B == 0:
        A_B.append((1, 0))
    else:
        if A < 0:
            A = -A
            B = -B
        C = math.gcd(abs(A), abs(B))
        A_B.append((A // C, B // C))

A_B_C = Counter(A_B)


ans = 1
Done = set([])
for key, value in A_B_C.items():
    if key in Done:
        continue
    keya, keyb = key
    a = 0
    if keyb < 0:
        keya = -keya
        keyb = -keyb
    if (keyb, -keya) not in A_B_C:
        a = pow(2, value, mod)
    else:
        a = (pow(2, value, mod) - 1) + (pow(2, A_B_C[(keyb, -keya)], mod) - 1) + 1
        Done.add((keyb, -keya))
    ans *= a
    ans %= mod
    Done.add(key)

print((ans - 1) % mod)