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 collections import defaultdict
from itertools import groupby, accumulate, product, permutations, combinations
from math import gcd
def reduction(x,y):
    g = gcd(x,y)
    return abs(x)//g,abs(y)//g

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:
            if y==0:
                N -= 1
            else:
                xzero += 1
        elif y==0:
            yzero += 1
        elif x*y>0:
            dplus[reduction(x,y)] += 1
        else:
            dminus[reduction(-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 math
MOD = 1000000007
N = int(input())
A = []
d = {}
for i in range(N):
	a,b = map(int,input().split())
	g = math.gcd(a,b)
	if a < 0:
		a *= -1
		b *= -1
	if a == 0 and b < 0:
		b *= -1
	if g != 0:
		a = a // g
		b = b // g
	if (a,b) in d:
		d[(a,b)] += 1
	else:
		d[(a,b)] = 1

ans_sp = 0
if (0,0) in d:
	ans_sp += d[(0,0)]

def pow(n, k):
	ret = 1
	while k > 0:
		if k % 2 == 1:
			ret = ret * n % MOD
		n = n * n % MOD
		k = k // 2
	return ret

ans = 1
for k in d:
	a,b = k[0], k[1]
	if a == 0 and b == 0:
		continue
	v = d[k]
	x,y = b,-a
	if x < 0:
		x *= -1
		y *= -1
	if (x,y) in d:
		if  b > y:
			continue
		tmp = (pow(2,v) + pow(2,d[(x,y)]) - 1) % MOD
		ans = (ans * tmp) % MOD
	else:
		ans = (ans * pow(2,v)) % MOD
print(ans_sp + ans - 1)

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)
    aa = 0
    for a, b in ab:
        if a == b == 0:
            aa += 1
            continue
        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
    ans += aa
    print(ans % mod)
    return


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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
import math
MOD = 10**9 + 7

n = int(input())
fish = dict() 
azero = 0
bzero = 0
abzero = 0
for _ in range(n):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        abzero += 1
        continue
    if a == 0:
        azero += 1
        continue
    if b == 0:
        bzero += 1
        continue
    a_abs = abs(a); b_abs = abs(b)
    g = math.gcd(a_abs, b_abs)
    if (a > 0 and b > 0) or (a < 0 and b < 0): 
        key = (a_abs // g, b_abs // g)
    else:
        key = (a_abs // g, -b_abs // g)
    if key not in fish:
        fish[key] = 1
    else:
        fish[key] += 1

ans = 1
for a, b in fish:
    if fish[(a, b)] == 0:
        continue
    if b < 0:
        inv_key = (-b, a)
    else:
        inv_key = (b, -a)
    if inv_key in fish:
        val1 = ans * (pow(2, fish[(a, b)], MOD) - 1)
        val2 = ans * (pow(2, fish[inv_key], MOD) - 1)
        fish[inv_key] = 0
        ans = val1 + val2 + ans
    else:
        val1 = ans * (pow(2, fish[(a, b)], MOD) - 1)
        ans = val1 + ans
    ans %= MOD
# think a == 0 or b == 0
val1 = ans * pow(2, azero, MOD) - 1
val2 = ans * pow(2, bzero, MOD) - 1
ans = val1 + val2 + ans
ans += abzero
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 bi==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:
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())
    rad = round(math.degrees(math.atan2(a, b)), 7)
    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 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 = (ans-1)%mod

print(ans)

Submission status: Wrong Answer

Solution code:
s = int(input())
G =[2019]
g = 2019
while g <= s:
    g += 2019
    G.append(g)
con = 0
print(len(G))
for i in G:
    #print(i)
    con += str(s).count(str(i))
print(con)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
INF=10**9+7
D={}
z=0
import math
for i in range(n):
    a,b=map(int,input().split())
    if a==0:
        if b==0:
            z+=1
        else:
            if (0,1) in D:
                D[(0,1)]+=1
            else:
                D[(0,1)]=1
    elif b==0:
        if (1, 0) in D:
            D[(1,0)] += 1
        else:
            D[(1,0)] = 1
    else:
        if b<0:
            b=-b
            a=-a
        if a>0:
            c=math.gcd(a,b)
            a//=c
            b//=c
            if (a,b) in D:
                D[(a,b)] += 1
            else:
                D[(a,b)] = 1
        else:
            a=-a
            c = math.gcd(a, b)
            a //= c
            b //= c
            a=-a
            if (a, b) in D:
                D[(a, b)] += 1
            else:
                D[(a, b)] = 1
ans=1
p=[1]
for i in range(n):
    temp=(p[-1]*2)%INF
    p.append(temp)
for i in D:
    if not D[i]==0:
        x=i[0]
        y=i[1]
        if x>0:
            if (-y,x) in D:
                temp=D[(-y,x)]
                D[(-y,x)]=0
                ans=(ans*(p[D[i]]+p[temp]-1))%INF
            else:
                ans=ans*p[D[i]]%INF
        else:
            if (y,-x) in D:
                temp=D[(y,-x)]
                D[(y,-x)]=0
                ans=(ans*(p[D[i]]+p[temp]-1))%INF
            else:
                ans=ans*p[D[i]]%INF
if z==0:
    ans=(z+ans-1)%INF
else:
    ans=(ans-1)%INF
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

gcd = lambda a, b: a if b == 0 else gcd(b, a%b)
mod = 10**9+7
N = int(input())
AB = [list(map(int, input().split())) for i in range(N)]
cnt = defaultdict(int)
for i, (A, B) in enumerate(AB):
    if A == B == 0:
        g = 1
    else:
        g = gcd(A, B)
    A //= g
    B //= g
    if cnt[(-A, -B)] > 0:
        a, b = -A, -B
    elif cnt[(-B, A)] > 0:
        a, b = -B, A
    elif cnt[(B, -A)] > 0:
        a, b = B, -A
    else:
        a, b = A, B
    cnt[(a, b)] += 1
ans = 0
f = 1
p = [None]*len(cnt)
vs = cnt.values()
for i, v in enumerate(vs):
    p[i] = pow(2, v, mod)    
    f = f * p[i] % mod
for i, v in enumerate(vs):
    f = f * pow(p[i], mod-2, mod) % mod
    ans += v * f
    ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
def gcd(a,b):
  while b:a,b=b,a%b
  return a
def xy(x,y):
  x,y=abs(x),abs(y)
  g=gcd(x,y)
  x//=g
  y//=g
  return (10**20)*x+y
from collections import defaultdict
mod=10**9+7
n=int(input())
aabb=[list(map(int,input().split()))for _ in range(n)]
ab=[]
for i in aabb:
  if i!=[0,0]:ab.append(i)
  else:n-=1
az=bz=0
d=defaultdict(int)
dd=defaultdict(int)
for i in ab:
  if 0 in i:
    if i[0]==0:az+=1
    else:bz+=1
  else:
    a,b=i
    if a*b>0:d[xy(a,b)]+=1
    else:dd[xy(a,b)]+=1
ans=pow(2,n,mod)-1
t=[]
tt=0
for i in dd:
  b,a=divmod(i,10**20)
  p,m=d[xy(a,b)],dd[i]
  if p*m:
    t.append((p,m))
    n-=p+m
    tt+=(p+m+1)
if az*bz:
  t.append((az,bz))
  n-=az+bz
  tt+=(az+bz+1)
for p,m in t:
  ttt=tt-(p+m)
  ans-=pow(2,n,mod)*ttt*(pow(2,p,mod)-1)*(pow(2,m,mod)-1)%mod
print(ans%mod)

Submission status: Wrong Answer

Solution code:
class Combination:
    """階乗とその逆元のテーブルをO(N)で事前作成し、組み合わせの計算をO(1)で行う"""
    def __init__(self, n, MOD):
        self.fact = [1]
        for i in range(1, n + 1):
            self.fact.append(self.fact[-1] * i % MOD)
        self.inv_fact = [0] * (n + 1)
        self.inv_fact[n] = pow(self.fact[n], MOD - 2, MOD)
        for i in reversed(range(n)):
            self.inv_fact[i] = self.inv_fact[i + 1] * (i + 1) % MOD
        self.MOD = MOD

    def factorial(self, k):
        """k!を求める O(1)"""
        return self.fact[k]

    def inverse_factorial(self, k):
        """k!の逆元を求める O(1)"""
        return self.inv_fact[k]

    def permutation(self, k, r):
        """kPrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r]) % self.MOD

    def combination(self, k, r):
        """kCrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.MOD

    def combination2(self, k, r):
        """kCrを求める O(r) kが大きいが、r <= nを満たしているときに使用"""
        if k < r:
            return 0
        res = 1
        for l in range(r):
            res *= (k - l)
            res %= self.MOD
        return (res * self.inv_fact[r]) % self.MOD


def compress(string):
    string.append(-2)
    n = len(string)
    begin, end, cnt = 0, 1, 1
    ans = []
    while end < n:
        if string[begin] == string[end]:
            end, cnt = end + 1, cnt + 1
        else:
            ans.append((string[begin], cnt))
            begin, end, cnt = end, end + 1, 1
    return ans

  
from collections import defaultdict


n = int(input())
info = [list(map(int, input().split())) for i in range(n)]
MOD = 10 ** 9 + 7
comb = Combination(10 ** 6, MOD)
res1 = []
res2 = []
ind = []
cnt_00 = 0
cnt_a0 = 0
cnt_b0 = 0
for i in range(n):
    a, b = info[i]
    if a == 0 and b == 0:
        cnt_00 += 1
        continue
    if a == 0:
        cnt_a0 += 1
        continue
    if b == 0:
        cnt_b0 += 1
        continue
    res1.append(a / b)
    res2.append(- b / a)
    ind.append(i)

memo_r = defaultdict(int)
memo_l = defaultdict(int)

for i in range(len(res1)):
    l, r = res1[i], res2[i]
    memo_r[r] += 1
    memo_l[l] += 1

ans = 1
used = set()
for r in memo_r:
    if r in used:
        continue
    cnt_r = memo_r[r]
    cnt_l = 0
    if r in memo_l:
        cnt_l += memo_l[r]
    tmp = (pow(2, cnt_l, MOD) - 1) + (pow(2, cnt_r, MOD) - 1) + 1
    ans *= tmp
    used.add(-1 / r)
print((ans - 1) % MOD)

Submission status: Wrong Answer

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9
    N=I()
    from math import gcd
    d={}
    for i in range(N):
        a,b=MI()
        if (a,b)!=(0,0):
            g=gcd(abs(a),abs(b))
            a=a//g
            b=b//g
        if (a,b) in d:
            d[(a,b)]+=1
        else:
            d[(a,b)]=1
        
    ans=1
    L=[]
    for k in d.keys():
        L.append((k,d[k]))


    for i in range(len(L)):
        k=L[i][0]
        v=d[k]
        d[k]=0
        temp=pow(2,v)
        a,b=k
        if a*b!=0:
            if (-b,a) in d:
                v2=d[(-b,a)]
                if v2!=0:
                    temp+=pow(2,v2)-1
                    d[(-b,a)]=0
            if (b,-a) in d:
                v2=d[(b,-a)]
                if v2!=0:
                    temp+=pow(2,v2)-1
                    d[(b,-a)]=0
        elif (a,b)!=(0,0):
            if (a,b)==(0,1):
                if (1,0) in d:
                    v2=d[(1,0)]
                    if v2!=0:
                        temp+=pow(2,v2)-1
                        d[(1,0)]=0
            elif (a,b)==(1,0):
                if (0,1) in d:
                    v2=d[(0,1)]
                    if v2!=0:
                        temp+=pow(2,v2)-1
                        d[(0,1)]=0
                    
                    
                        
                
        
        ans=(ans*temp)%mod
        
        
        

        
    print(ans-1)
        
        
            
            
    #せんぶ０の組みをひく
        
    

main()

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import defaultdict

n = int(readline())
data = list(map(int,read().split()))
mod = 1000000007

it = iter(data)
a_b = defaultdict(lambda :[0,0])
a0 = 0
b0 = 0
ab0 = 0
ans = 0
for a,b in zip(it,it):
    if(a==b==0):
        ab0 += 1
        continue
    if(a*b==0):
        if(a==0):
            a0 += 1
        if(b==0):
            b0 += 1
    else:
        if(a/b > 0):
            a_b[a/b][0] += 1
        else:
            a_b[-1*b/a][1] += 1

exp2 = [1] * (n+1)
for i in range(n):
    exp2[i+1] = exp2[i] * 2
    exp2[i+1] %= mod


ans += (ans+1) * ( exp2[a0]-1  + exp2[b0]-1)
ans %= mod

for key,val in a_b.items():
    ans += (ans+1) * ( exp2[val[0]]-1  + exp2[val[1]]-1)
    ans %= mod

ans += ab0
ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))

from collections import defaultdict, deque
from sys import exit
import math
import copy
from bisect import bisect_left, bisect_right
from heapq import *
import sys
# sys.setrecursionlimit(1000000)
INF = 10 ** 17
MOD = 1000000007
 
from fractions import *
def inverse(f):
    return Fraction(f.denominator,f.numerator)


def combmod(n, k, mod=MOD):
    ret = 1
    for i in range(n - k + 1, n + 1):
        ret *= i
        ret %= mod

    for i in range(1, k + 1):
        ret *= pow(i, mod - 2, mod)
        ret %= mod

    return ret

def solve():
    n = getN()
    iwashis = []
    for i in range(n):
        iwashis.append(getList())

    fr = defaultdict(int)
    for iw in iwashis:
        if iw[0] != 0:
            fr[Fraction(iw[1], iw[0])] += 1
        else:
            fr["INF"] += 1

    used = defaultdict(int)
    ans = 1
    for k, v in fr.items():
        if k in used:
            continue
        if k == "INF":
            if 0 in fr:
                ans *= pow(2, v, MOD) + pow(2, fr[0], MOD) - 1
                ans %= MOD
            else:
                ans *= pow(2, v, MOD)
                ans %= MOD
            used[0] += 1
        elif k != 0:
            if - inverse(k) in fr:
                ans *= pow(2, v, MOD) + pow(2, fr[- inverse(k)], MOD) - 1
                ans %= MOD
            else:
                ans *= pow(2, v, MOD)
                ans %= MOD
            used[- inverse(k)] += 1
        elif k == 0:
            if "INF" in fr:
                ans *= pow(2, v, MOD) + pow(2, fr["INF"], MOD) - 1
                ans %= MOD
            else:
                ans *= pow(2, v, MOD)
                ans %= MOD
            used["INF"] += 1
        # print(k, v, ans, -inverse(k))
    # print(fr)
    print((ans-1) % MOD)
    # print(Fraction(0, ???1) == 0)

def main():
    n = getN()
    for _ in range(n):
        solve()
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
def gcd(a,b):
  while b:a,b=b,a%b
  return a
def xy(x,y):
  x,y=abs(x),abs(y)
  g=gcd(x,y)
  x//=g
  y//=g
  return (10**20)*x+y
from collections import defaultdict
mod=10**9+7
n=int(input())
aabb=[list(map(int,input().split()))for _ in range(n)]
ab=[]
for i in aabb:
  if i!=[0,0]:ab.append(i)
  else:n-=1
az=bz=0
d=defaultdict(int)
dd=defaultdict(int)
for i in ab:
  if 0 in i:
    if i[0]==0:az+=1
    else:bz+=1
  else:
    a,b=i
    if a*b>0:d[xy(a,b)]+=1
    else:dd[xy(a,b)]+=1
ans=pow(2,n,mod)-1
ans-=az*bz
t=[]
tt=0
for i in dd:
  b,a=divmod(i,10**20)
  p,m=d[xy(a,b)],dd[i]
  if p*m:
    t.append((p,m))
    n-=p+m
    tt+=(p+m+1)
for p,m in t:
  ttt=tt-(p+m)
  ans-=pow(2,n,mod)*ttt*(pow(2,p,mod)-1)*(pow(2,m,mod)-1)%mod
print(ans%mod)

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])-1 + 2**(zeros[1])-1 + 1
#print(zerok)

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

answer=1
#print(slist)

rev=0

for sl in slist:
    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
    mae=sl
    #print(answer)
#print(onaji)

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:
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
print(NonZero -1 )

Submission status: Wrong Answer

Solution code:
from fractions import Fraction



a = int(input())
resab = dict()
resba = dict()
res0 = 0

for i in range(a):
    ai, bi = [int(i) for i in input().split()]
    if ai != 0 and bi != 0:
        if Fraction(ai, bi) not in resab:
            resab[Fraction(ai, bi)] = 1
        else:
            resab[Fraction(ai, bi)] += 1
        if Fraction(-bi, ai) not in resba:
            resba[Fraction(-bi, ai)] = 1
        else:
            resba[Fraction(-bi, ai)] += 1
    else:
        res0 += 1

# print(resab)
# print(resba)
# print(res0)
ans = 1
for i in list(resab.keys()):
    if i in resba and i in resab:
        ans *= (2**resab[i] - 1 + 2**resba[i]) 
        #print(ans, i)
        del resab[i]
        del resab[Fraction(-i.denominator, i.numerator)]
        del resba[i]
        del resba[Fraction(-i.denominator, i.numerator)]
    elif i in resba:
        ans *= resba[i] + 1
        #print(ans, i)
        del resba[i]
        try:
            del resab[Fraction(-i.denominator, i.numerator)]
        except:
            pass
    elif i in resab:
        ans *= resab[i] + 1
        #print(ans, i)
        del resab[i]
        try:
            del resba[Fraction(-i.denominator, i.numerator)]
        except:
            pass
        
    ans %= 1000000007

ans *= (res0 + 1)
ans -= 1
ans %= 1000000007
print(ans)

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 *= (MOD + pow(2, x, MOD) + pow(2, y, MOD) - 1) % MOD
        ans %= MOD

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

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

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [list(map(int,input().split())) for i in range(n)]
s = 0
for i in range(n):
  for j in range(i+1, n):
    if a[i][0]*a[j][0] + a[i][1]*a[j][1] == 0:
      s += 1
ans = 2**n - 1 - s * 2**(n-2)
print(ans)

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)
C00 = 0
C0 = 0
for i in range(N):
    a, b = map(int, input().split())
    if a == b == 0:
        C00 += 1
    elif 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 + C00 - 1) % mod)