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
#E

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def comb(n, r):
    return fact[n]*pow(fact[n-r], mod-2, mod)*pow(fact[r], mod-2, mod) % mod
n = I()
ab = [LI() for _ in range(n)]

fact = [1]*(n+1)
for i in range(1, n+1):
    fact[i] = i * fact[i-1]
    fact[i] %= mod

x = []
y = []
tmp = 0
for a, b in ab:
    if a == 0 and b == 0:
        tmp += 1
    elif a == 0:
        x.append(0)
        y.append(-inf)
    elif b == 0:
        x.append(inf)
        y.append(0)
    else:
        x.append(a/b)
        y.append(-b/a)


z = defaultdict(lambda : 0)
w = defaultdict(lambda : 0)
ans = 0
for i,j in enumerate(x):
    if z[j]:
        w[j] += 1
        continue
    z[y[i]] += 1

ans = 1
for i, j in z.items():
    ans *= (2**j + 2**w[i] - 1)
    ans %= mod
ans -= 1
ans += tmp
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#E

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def comb(n, r):
    return fact[n]*pow(fact[n-r], mod-2, mod)*pow(fact[r], mod-2, mod) % mod
n = I()
ab = [LI() for _ in range(n)]
ans = pow(2, n, mod) - 1
fact = [1]*(n+1)
for i in range(1, n+1):
    fact[i] = i * fact[i-1]
    fact[i] %= mod

x = []
y = []
for a, b in ab:
    if a == 0 and b == 0:
        ans -= pow(2, n-1, mod) - 1
        ans %= mod
        n -= 1
    elif a == 0:
        x.append(0)
        y.append(-inf)
    elif b == 0:
        x.append(inf)
        y.append(0)
    else:
        x.append(a/b)
        y.append(-b/a)
lst = defaultdict(lambda : 0)
z = defaultdict(lambda : 0)
for i,j in enumerate(x):
    if z[j]:
        lst[j] = max(lst[j], z[j]+1)
    z[y[i]] += 1

for i in lst.values():
    j = 0
    while j + 1 < i:
        if n - (i-(j+2)) - (j+2) >= 0:
            ans -= comb(i, j+2) * pow(2, n - (i-(j+2)) - (j+2), mod)
            ans %= mod
        j += 1
    n -= i
    if n <= 0:
        break
print(ans)

Submission status: Wrong Answer

Solution code:
# 約分して、互いに素な(1,3) (3,1)のようなペアを作りカウントする
# 正のグループと負のグループを別々に管理
# 正のグループの相手が負のグループに存在した場合、
# どちらかのグループから好きなだけ選ぶか、どちらも選ばないかしかない
# 誰ともペアにならなかったグループの個数を全て足してP個だとして、2^P通りを掛ける
# (0,0)については、その中から1つ選ぶか、選ばないかしかない

import sys
readline = sys.stdin.readline

N = int(readline())
import math

zeropair = 0
zeroa = 0
zerob = 0
from collections import defaultdict
pluspair = defaultdict(int)
minuspair = defaultdict(int)
for i in range(N):
  a,b = map(int,readline().split())
  if a == 0 and b == 0:
    zeropair += 1
    continue
  if a == 0:
    zeroa += 1
    continue
  if b == 0:
    zerob += 1
    continue
  absa = abs(a)
  absb = abs(b)
  g = math.gcd(absa,absb)
  absa,absb = absa//g,absb//g
  if a * b > 0:
    pluspair[(absa,absb)] += 1
  else:
    minuspair[(absa,absb)] += 1

DIV = 1000000007
ans = 1
# zeroa,zerobから選ぶパターンは、どちらから好きなだけ選ぶか、どちらも選ばないか
ans *= (pow(2,zeroa,DIV) + pow(2,zerob,DIV) - 1) % DIV
ans %= DIV

# 誰とでもペアになれるものをカウント
allcnt = 0

# plusから選ぶパターンで、minusにある対応ペアを探す
for item in pluspair.items():
  a,b = item[0]
  cnt = item[1]
  if (b,a) in minuspair:
    ans *= (pow(2,cnt,DIV) + pow(2,minuspair[(b,a)]) - 1) % DIV
    ans %= DIV
    del minuspair[(b,a)]
  else:
    allcnt += 1

for val in minuspair.values():
  allcnt += val

ans = (ans * pow(2,allcnt,DIV)) % DIV
# zeropairから選んだ場合、今までのパターンとは独立
ans += zeropair
print((ans - 1) % DIV)

Submission status: Wrong Answer

Solution code:
# 約分して、互いに素な(1,3) (3,1)のようなペアを作りカウントする
# 正のグループと負のグループを別々に管理
# 正のグループの相手が負のグループに存在した場合、
# どちらかのグループから好きなだけ選ぶか、どちらも選ばないかしかない
# 誰ともペアにならなかったグループの個数を全て足してP個だとして、2^P通りを掛ける
# (0,0)については、その中から1つ選ぶか、選ばないかしかない

import sys
readline = sys.stdin.readline

N = int(readline())
import math

zeropair = 0
zeroa = 0
zerob = 0
from collections import defaultdict
pluspair = defaultdict(int)
minuspair = defaultdict(int)
for i in range(N):
  a,b = map(int,readline().split())
  if a == 0 and b == 0:
    zeropair += 1
    continue
  if a == 0:
    zeroa += 1
    continue
  if b == 0:
    zerob += 1
    continue
  absa = abs(a)
  absb = abs(b)
  g = math.gcd(absa,absb)
  absa,absb = absa//g,absb//g
  if a * b > 0:
    pluspair[(absa,absb)] += 1
  else:
    minuspair[(absa,absb)] += 1

DIV = 1000000007
ans = 1
# zeroa,zerobから選ぶパターンは、どちらから好きなだけ選ぶか、どちらも選ばないか
ans *= (pow(2,zeroa,DIV) + pow(2,zerob,DIV) - 1)
ans %= DIV

# 誰とでもペアになれるものをカウント
allcnt = 0

# plusから選ぶパターンで、minusにある対応ペアを探す
for item in pluspair.items():
  a,b = item[0]
  cnt = item[1]
  if (b,a) in minuspair:
    ans *= (pow(2,cnt,DIV) + pow(2,minuspair[(b,a)]) - 1)
    ans %= DIV
    del minuspair[(b,a)]
  else:
    allcnt += 1

for val in minuspair.values():
  allcnt += val

ans = (ans * pow(2,allcnt,DIV)) % DIV

# zeropairから選んだ場合、今までのパターンとは独立
ans += zeropair
print((ans - 1) % DIV)

Submission status: Wrong Answer

Solution code:
# 約分して、互いに素な(1,3) (3,1)のようなペアを作りカウントする
# 正のグループと負のグループを別々に管理
# 正のグループの相手が負のグループに存在した場合、
# どちらかのグループから好きなだけ選ぶか、どちらも選ばないかしかない
# 誰ともペアにならなかったグループの個数を全て足してP個だとして、2^P通りを掛ける
# (0,0)については、その中から1つ選ぶか、選ばないかしかない

import sys
readline = sys.stdin.readline

N = int(readline())
import math

zeropair = 0
zeroa = 0
zerob = 0
from collections import defaultdict
pluspair = defaultdict(int)
minuspair = defaultdict(int)
for i in range(N):
  a,b = map(int,readline().split())
  if a == 0 and b == 0:
    zeropair += 1
    continue
  if a == 0:
    zeroa += 1
    continue
  if b == 0:
    zerob += 1
    continue
  absa = abs(a)
  absb = abs(b)
  g = math.gcd(absa,absb)
  absa,absb = absa//g,absb//g
  if a * b > 0:
    pluspair[(absa,absb)] += 1
  else:
    minuspair[(absa,absb)] += 1

DIV = 1000000007
ans = 1
# zeroa,zerobから選ぶパターンは、どちらから好きなだけ選ぶか、どちらも選ばないか
ans *= (pow(2,zeroa,DIV) + pow(2,zerob,DIV) - 1)
ans %= DIV

# 誰とでもペアになれるものをカウント
allcnt = 0

# plusから選ぶパターンで、minusにある対応ペアを探す
for item in pluspair.items():
  a,b = item[0]
  cnt = item[1]
  if (b,a) in minuspair:
    ans *= (pow(2,cnt,DIV) + pow(2,minuspair[(b,a)]) - 1)
    ans %= DIV
    del minuspair[(b,a)]
  else:
    allcnt += 1

for val in minuspair.values():
  allcnt += val

ans = (ans * pow(2,allcnt,DIV)) % DIV

# zeropairから選んだ場合、今までのパターンとは独立
ans += zeropair

print(ans - 1)

Submission status: Wrong Answer

Solution code:
# 約分して、互いに素な(1,3) (3,1)のようなペアを作りカウントする
# 正のグループと負のグループを別々に管理
# 正のグループの相手が負のグループに存在した場合、
# どちらかのグループから好きなだけ選ぶか、どちらも選ばないかしかない
# 誰ともペアにならなかったグループの個数を全て足してP個だとして、2^P通りを掛ける
# (0,0)については、その中から1つ選ぶか、選ばないかしかない

import sys
readline = sys.stdin.readline

N = int(readline())
import math

zeropair = 0
zeroa = 0
zerob = 0
from collections import defaultdict
pluspair = defaultdict(int)
minuspair = defaultdict(int)
for i in range(N):
  a,b = map(int,readline().split())
  if a == 0 and b == 0:
    zeropair += 1
    continue
  if a == 0:
    zeroa += 1
    continue
  if b == 0:
    zerob += 1
    continue
  absa = abs(a)
  absb = abs(b)
  g = math.gcd(absa,absb)
  absa,absb = absa//g,absb//g
  if a * b > 0:
    pluspair[(absa,absb)] += 1
  else:
    minuspair[(absa,absb)] += 1

DIV = 1000000007
ans = 1
# zeropairから選ぶパターンは、zeropairの数 + 1
ans *= (zeropair + 1)
ans %= DIV
# zeroa,zerobから選ぶパターンは、どちらから好きなだけ選ぶか、どちらも選ばないか
ans *= (pow(2,zeroa,DIV) + pow(2,zerob,DIV) - 1)
ans %= DIV

# 誰とでもペアになれるものをカウント
allcnt = 0

# plusから選ぶパターンで、minusにある対応ペアを探す
for item in pluspair.items():
  a,b = item[0]
  cnt = item[1]
  if (b,a) in minuspair:
    ans *= (pow(2,cnt,DIV) + pow(2,minuspair[(b,a)]) - 1)
    ans %= DIV
    del minuspair[(b,a)]
  else:
    allcnt += 1

for val in minuspair.values():
  allcnt += val

ans = (ans * pow(2,allcnt,DIV)) % DIV
print(ans - 1)

Submission status: Wrong Answer

Solution code:
import sys
import collections
import fractions
import math
def input():
    return sys.stdin.readline()[:-1]
n=int(input())
zero = 0
dic = {}
mod = 10**9+7
for i in range(n):
    a,b = map(int,input().split())
    rt =0
    if a==0 and b==0:
        zero+=1
        continue
    g = math.gcd(a,b)
    a = int(a/g)
    b = int(b/g)
    if b<0:
        a=-a
        b=-b
    if a<0 and b==0:
        a=-a
        b=-b
    if a<=0:
        rt=1
        a,b = b,-a

    if (a,b) not in dic:
        if rt==0:
            dic[(a,b)] = [1,0]
        else:
            dic[(a,b)] = [0,1]
    else:
        if rt==0:
            dic[(a,b)][0] += 1
        else:
            dic[(a,b)][1] += 1

ans = 1
for i,j in dic.values():
    tmp = pow(2,i,mod) - 1
    tmp2 = pow(2,j,mod) - 1
    su = (tmp+tmp2+1)%mod
    ans = (ans*su)%mod

ans = (ans-1+zero)%mod

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import collections
import fractions
import math
def input():
    return sys.stdin.readline()[:-1]
n=int(input())
zero = 0
dic = {}
mod = 10**9+7
for i in range(n):
    a,b = map(int,input().split())
    rt =0
    if a==0 and b==0:
        zero+=1
        continue
    if b<0:
        a=-a
        b=-b
    if a<0 and b==0:
        a=-a
        b=-b
    if a<=0 and b>0:
        rt=1
        a,b = b,-a
    g = math.gcd(a,b)
    a = int(a/g)
    b = int(b/g)
    if (a,b) not in dic:
        if rt==0:
            dic[(a,b)] = [1,0]
        else:
            dic[(a,b)] = [0,1]
    else:
        if rt==0:
            dic[(a,b)][0] += 1
        else:
            dic[(a,b)][1] += 1

ans = 1
for i,j in dic.values():
    tmp = pow(2,i,mod) - 1
    tmp2 = pow(2,j,mod) - 1
    #print(tmp,tmp2)
    ans *= (tmp+tmp2+1)
    ans %= mod

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

Submission status: Wrong Answer

Solution code:
import sys
import collections
import fractions
import math
def input():
    return sys.stdin.readline()[:-1]
n=int(input())
zero = 0
dic = {}
mod = 10**9+7
for i in range(n):
    a,b = map(int,input().split())
    rt =0
    if a==0 and b==0:
        zero+=1
        continue
    if b<0:
        a=-a
        b=-b
    if a<0 and b==0:
        a=-a
        b=-b
    if a<=0 and b>0:
        rt=1
        a,b = b,-a
    g = math.gcd(a,b)
    a = int(a/g)
    b = int(b/g)
    if (a,b) not in dic:
        if rt==0:
            dic[(a,b)] = [1,0]
        else:
            dic[(a,b)] = [0,1]
    else:
        if rt==0:
            dic[(a,b)][0] += 1
        else:
            dic[(a,b)][1] += 1

ans = 1
for i,j in dic.values():
    tmp = pow(2,i,mod) - 1
    tmp2 = pow(2,j,mod) - 1
    #print(tmp,tmp2)
    ans *= (tmp+tmp2+1)
    ans %= mod

ans = ans-1+zero
print(ans)

Submission status: Wrong Answer

Solution code:
import sys, bisect, collections, math
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
MOD = 1000000007
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N = I()
    AB = [LI() for _ in range(N)]

    # A, Bを標準化 互いに疎でAは正
    def normalize(AB):
        A = AB[0]
        B = AB[1]
        if A==B==0:
            return (0, 0)
        elif A==0:
            return(0, 1)
        elif B==0:
            return(1, 0)
        else:
            gcd = math.gcd(A, B)
            A //= gcd
            B //= gcd
            if A<0:
                A, B = -A, -B
            return (A, B)
    
    def orthogonal(AB):
        A = AB[0]
        B = AB[1]
        if B>0:
            return (B, -A)
        else:
            return(-B, A)

    AB_n = [normalize(i) for i in AB]
    counter = collections.Counter(AB_n)

    # 場合の数を求める
    used = set()
    ans = 1
    # (0, 0)以外について
    for A, B in AB_n:
        if not (A, B) in used:
            if (A, B)!=(0, 0):
                ans *= 2**counter[(A, B)]+2**counter[orthogonal((A, B))]-1
                ans %= MOD
                used.add((A, B))
                used.add(orthogonal((A, B)))
    ans -= 1
    # (0, 0)について
    ans += 2**counter[(0, 0)]-1
    ans %= MOD

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
from math import gcd

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

zero = 0
for _ in range(N):
    a,b = map(int, input().split())
    if  a == b == 0:
        zero += 1
        continue
    elif a == 0:
        key = (0,1)
    elif b == 0:
        key = (1,0)
    else:
        if a<0:
            a=-a 
            b=-b
        g = gcd(a,abs(b))
        key = (a//g,b//g)
    
    if key not in dic:
        dic[key]=0

    dic[key] +=1

ans = 1
for k1, v1 in dic.items():
    if v1 ==0:
        continue

    if k1[1] >0:
        k2 = (k1[1],-k1[0])
    else:
        k2 = (-k1[1],k1[0])

    if k2 not in dic:
        ans *= 2**v1
        ans %= mod
    else:
        ans *= (2**v1-1 %mod) + (2**dic[k2]-1 %mod) + 1
        ans %= mod
        dic[k2]=0

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

Submission status: Wrong Answer

Solution code:
from math import gcd

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

zero = 0
for _ in range(N):
    a,b = map(int, input().split())
    if  a == b == 0:
        zero += 1
        continue
    elif a == 0:
        key = (0,1)
    elif b == 0:
        key = (1,0)
    else:
        if a<0:
            a=-a 
            b=-b
        g = gcd(a,abs(b))
        key = (a//g,b//g)
    
    if key not in dic:
        dic[key]=0

    dic[key] +=1

ans = 1
for k1, v1 in dic.items():
    if v1 ==0:
        continue

    if k1[1] >0:
        k2 = (k1[1],-k1[0])
    else:
        k2 = (-k1[1],k1[0])

    if k2 not in dic:
        ans *= 2**v1
        ans %= mod
    else:
        ans *= (2**v1-1) + (2**dic[k2]-1) + 1
        ans %= mod
        dic[k2]=0

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

Submission status: Wrong Answer

Solution code:
import sys
def input(itr=iter(sys.stdin.readlines())):  # pylint: disable= redefined-builtin
    return next(itr).rstrip('\n\r')
###############################################################################

import collections
import math as m
from fractions import Fraction

MOD = 1000000007

N = int(input())
Sardine = collections.namedtuple("Sardine", "A B")
sardines = [Sardine(*map(int, input().split())) for _ in range(N)]

def slope(sardine):
    if sardine.A == sardine.B == 0:
        return None
    elif sardine.B == 0:
        return m.inf
    else:
        return Fraction(sardine.A, sardine.B)

def perpendicular(slope):
    if slope == 0:
        return m.inf
    elif slope == m.inf:
        return 0
    else:
        return -1 / slope

groups = collections.Counter(slope(s) for s in sardines)
del groups[None]

ways = 1
while groups:
    slope, count = groups.popitem()
    perp_slope = perpendicular(slope)
    perp_count = groups[perp_slope]

    ways *= ((1<<count) + (1<<perp_count) - 1) % MOD
    ways %= MOD

    del groups[perp_slope]

print((ways-1)%MOD)

Submission status: Wrong Answer

Solution code:
import sys
def input(itr=iter(sys.stdin.readlines())):  # pylint: disable= redefined-builtin
    return next(itr).rstrip('\n\r')
###############################################################################

import collections
import math as m
from fractions import Fraction

MOD = 1000000007

N = int(input())
Sardine = collections.namedtuple("Sardine", "A B")
sardines = [Sardine(*map(int, input().split())) for _ in range(N)]

def slope(sardine):
    if sardine.A == sardine.B == 0:
        return None
    elif sardine.B == 0:
        return m.inf
    else:
        return Fraction(sardine.A, sardine.B)

def perpendicular(slope):
    if slope == 0:
        return m.inf
    elif slope == m.inf:
        return 0
    else:
        return -1 / slope

groups = collections.Counter()
for s in sardines:
    groups[slope(s)] += 1

ways = 1
if groups[None]:
    ways *= 2
    del groups[None]

while groups:
    slope, count = groups.popitem()
    perp_slope = perpendicular(slope)
    perp_count = groups[perp_slope]

    ways *= (2**count + 2**perp_count - 1) % MOD
    ways %= MOD

    del groups[perp_slope]

print((ways-1)%MOD)

Submission status: Wrong Answer

Solution code:
import sys
def input(itr=iter(sys.stdin.readlines())):  # pylint: disable= redefined-builtin
    return next(itr).rstrip('\n\r')
###############################################################################

import collections
import math as m
from fractions import Fraction

MOD = 1000000007

N = int(input())
Sardine = collections.namedtuple("Sardine", "A B")
sardines = [Sardine(*map(int, input().split())) for _ in range(N)]

def slope(sardine):
    if sardine.B == 0:
        return m.inf
    else:
        return Fraction(sardine.A, sardine.B)

def perpendicular(slope):
    if slope == 0:
        return m.inf
    elif slope == m.inf:
        return 0
    else:
        return -1 / slope

groups = collections.Counter()
for s in sardines:
    groups[slope(s)] += 1

ways = 1
while groups:
    slope, count = groups.popitem()
    perp_slope = perpendicular(slope)
    perp_count = groups[perp_slope]

    ways *= (2**count + 2**perp_count - 1) % MOD
    ways %= MOD

    del groups[perp_slope]

print((ways-1)%MOD)

Submission status: Wrong Answer

Solution code:
# from collections import deque as dq
# import itertools
import math
# import matplotlib.pyplot as plt
# import networkx as nx
# import numpy as np
import sys
input = sys.stdin.readline


def select_num(a, b, mod=1000000007):
    sum = pow(2, a, mod) + pow(2, b, mod) - 1
    return sum % mod


def dict_count(d, a, b):
    this = a / b
    pair = b / a
    if not d.get(this, False):
        d[this] = {"num": 0, "pair": pair}
    d[this]["num"] += 1


def main():
    MOD = 1000000007
    n = int(input())

    a_div_b = {}
    a0 = b0 = zero = 0
    for i in range(n):
        a, b = map(int, input().split())
        if a == 0 or b == 0:
            if a == b == 0:
                n -= 1
                zero += 1
            elif a == 0:
                a0 += 1
            elif b == 0:
                b0 += 1
            continue

        gcd = math.gcd(a, b)
        a //= gcd
        b //= gcd
        dict_count(a_div_b, a, b)

    ans = 1
    cnt = 0
    # print(a_div_b)
    while a_div_b:
        cnt += 1
        _, inner_dict = a_div_b.popitem()
        a_count = inner_dict["num"]
        pair = inner_dict["pair"] * -1
        b_count = a_div_b.get(pair, {}).get("num")
        # print(f"{a_count = }, {b_count = }\n{ans = }, {_ = }")
        if b_count:
            ans *= select_num(a_count, b_count, MOD)
            ans %= MOD
            cnt -= 1
            del a_div_b[pair]
            # print(f"{_ = }, {a_count = }, {b_count = }\n{ans = }")
    else:
        ans *= select_num(a0, b0, MOD)
        ans *= pow(2, cnt, MOD)
        ans += zero - 1
        ans %= MOD

    # print(f"{a_div_b = }")
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from math import gcd
mod = 1000000007
n = int(input())
zero = 0
bad = {}
for i in range(n):
    a,b = map(int, input().split())

    if a == 0 and b == 0:
        zero += 1
        continue

    if a != 0 or b != 0:
        g = gcd(a, b)
        a //= g
        b //= g

    is_minus = True
    if a>0 and b>0 : is_minus = False
    if a<0 and b<0 : is_minus = False
    sign_ab = -1 if is_minus else 1
    sign_cd = 1 if is_minus else -1
    d, c = a, b = abs(a), abs(b)
    key1 = (sign_ab*a, b)
    key2 = (sign_cd*c, d)

    if key1 in bad: bad[key1][0] += 1
    elif key2 in bad: bad[key2][1] += 1
    else: bad[key1] = [1,0]

cnt = 1
for a,b in bad:
    c1, c2 = bad[a, b]
    c3 = 0
    c3 += pow(2, c1, mod) - 1
    c3 += pow(2, c2, mod) - 1
    c3 += 1
    cnt = cnt * c3 % mod

ans = (cnt + zero - 1) % mod

# print('cnt',cnt)
# print('zero',zero)
# print('ans',ans)
print((ans+mod) % mod)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import math
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10**8)
INF = float("inf")

MOD = 1000000007  # type: int


def solve(N: int, A: "List[int]", B: "List[int]"):
    # 直交するイワシは選べない。
    # 順にイワシを見て、直行するものをグループにする。
    # 先に単純な整数比へ変換しておく（有理数としての扱い）
    # aは整数、bは非負整数となるように整理する
    d = Counter()
    # (a, b) == (0, 0)については、他のイワシと同時に選ぶことができない。
    # 個別にカウントする。
    kodokunaiwashi = 0
    for i, (a, b) in enumerate(zip(A, B)):
        if a == 0 and b == 0:
            kodokunaiwashi += 1
        elif b == 0:
            d[1, 0] += 1
        elif b > 0:
            g = math.gcd(b, a)
            aa = a//g
            bb = b//g
            d[aa, bb] += 1
        else:
            g = math.gcd(-b, -a)
            aa = -a//g
            bb = -b//g
            d[(aa, bb)] += 1

    # 直交するグループを考える。
    ans = 1
    for a, b in d:
        # (a, b)と直交するのは、(-b, a)と(b, -a)である。
        # このうち、有理数としてカウントしている方を採用する
        x, y = -b, a
        if y < 0:
            x = -x
            y = -y

        # すでに直交するイワシとしてカウントをしたらNoneとしている。
        if d[a, b] == None:
            continue

        if d[x, y] == 0:
            # 直交するイワシが存在しない場合、自由に選ぶことができる。
            ans *= pow(2, d[a, b], MOD)
            ans %= MOD
            continue
        else:
            # 直交するイワシが存在する場合、どちらかのグループから自由に選ぶ。
            # ただし、一つも選ばないという場合は、重複するためケア
            buf = pow(2, d[a, b], MOD)
            buf += pow(2, d[x, y], MOD)
            buf -= 1
            buf %= MOD
            # print(buf)
            ans *= buf
            ans %= MOD
            d[x, y] = None

    print((ans-1+kodokunaiwashi) % MOD)

    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
sys.setrecursionlimit(10000)
# print(sys.getrecursionlimit())

from math import gcd
mod = 1000000007
n = int(input())
zero = 0
bad = {}
for i in range(n):
    a,b = map(int, input().split())

    if a == 0 and b == 0:
        zero += 1
        continue

    if a != 0 or b != 0:
        g = gcd(a, b)
        a //= g
        b //= g

    is_minus = True
    if a>0 and b>0 : is_minus = False
    if a<0 and b<0 : is_minus = False
    sign_ab = -1 if is_minus else 1
    sign_cd = 1 if is_minus else -1
    d, c = a, b = abs(a), abs(b)
    key1 = (sign_ab*a, b)
    key2 = (sign_cd*c, d)

    if key1 in bad: bad[key1][0] += 1
    elif key2 in bad: bad[key2][1] += 1
    else: bad[key1] = [1,0]


# a^n mod m を計算する(繰り返し二乗法,二分累乗法:O(logn)) (再帰版)
def modpow(a, n):
    global mod
    if n > 0: return modpow(a*a%mod, n//2) * (a if n%2 else 1) % mod
    else: return 1

cnt = 1
for a,b in bad:
    c1, c2 = bad[a, b]
    c3 = modpow(2, c1) - 1
    c3 += modpow(2, c2) - 1
    c3 += 1
    cnt = cnt * c3 % mod

ans = (cnt + zero - 1) % mod

# print('cnt',cnt)
# print('zero',zero)
# print('ans',ans)
print((ans+mod) % mod)

Submission status: Wrong Answer

Solution code:
from math import gcd
mod = 1000000007
n = int(input())
zero = 0
bad = {}
for i in range(n):
    a,b = map(int, input().split())

    if a == 0 and b == 0:
        zero += 1
        continue

    if a != 0 and b != 0:
        g = gcd(a, b)
        a //= g
        b //= g

    is_minus = True
    if a>0 and b>0 : is_minus = False
    if a<0 and b<0 : is_minus = False
    sign_ab = -1 if is_minus else 1
    sign_cd = 1 if is_minus else -1
    d, c = a, b = abs(a), abs(b)
    key1 = (sign_ab*a, b)
    key2 = (sign_cd*c, d)

    if key1 in bad: bad[key1][0] += 1
    elif key2 in bad: bad[key2][1] += 1
    else: bad[key1] = [1,0]


# a^n mod m を計算する(繰り返し二乗法,二分累乗法:O(logn)) (再帰版)
def modpow(a, n):
    global mod
    if n > 0: return modpow(a*a%mod,n//2) * (a if n%2 else 1) % mod
    else: return 1

cnt = 1
for a,b in bad:
    c1, c2 = bad[a, b]
    # c3 = (2**c1 - 1) % mod
    # c3 += (2**c2 - 1) % mod
    c3 = modpow(2, c1) - 1
    c3 += modpow(2, c2) - 1
    c3 += 1
    cnt = cnt * c3 % mod

ans = (cnt + zero - 1 + mod) % mod

# print('cnt',cnt)
# print('zero',zero)
# print('ans',ans)
print(ans)

Submission status: Wrong Answer

Solution code:
from math import gcd
mod = 1000000007
n = int(input())
zero = 0
bad = {}
for i in range(n):
    a,b = map(int, input().split())

    if a == 0 and b == 0:
        zero += 1
        continue

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

    is_minus = True
    if a>0 and b>0 : is_minus = False
    if a<0 and b<0 : is_minus = False
    sign_ab = -1 if is_minus else 1
    sign_cd = 1 if is_minus else -1
    d, c = a, b = abs(a), abs(b)
    key1 = (sign_ab*a, b)
    key2 = (sign_cd*c, d)

    if key1 in bad: bad[key1][0] += 1
    elif key2 in bad: bad[key2][1] += 1
    else: bad[key1] = [1,0]


# a^n mod m を計算する(繰り返し二乗法,二分累乗法:O(logn)) (再帰版)
def modpow(a, n):
    global mod
    if n > 0: return modpow(a*a%mod,n//2) * (a if n%2 else 1) % mod
    else: return 1

cnt = 1
for a,b in bad:
    c1, c2 = bad[a, b]
    # c3 = (2**c1 - 1) % mod
    # c3 += (2**c2 - 1) % mod
    c3 = modpow(2, c1) - 1
    c3 += modpow(2, c2) - 1
    c3 += 1
    cnt = cnt * c3 % mod

ans = (cnt + zero - 1 + mod) % mod

# print('cnt',cnt)
# print('zero',zero)
# print('ans',ans)
print(ans)

Submission status: Wrong Answer

Solution code:
from math import gcd
mod = 1000000007
n = int(input())
zero = 0
bad = {}
for i in range(n):
    a,b = map(int, input().split())

    if a == 0 and b == 0:
        zero += 1
        continue

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

    is_minus = True
    if a>0 and b>0 : is_minus = False
    if a<0 and b<0 : is_minus = False
    sign_ab = -1 if is_minus else 1
    sign_cd = 1 if is_minus else -1
    d, c = a, b = abs(a), abs(b)
    key1 = (sign_ab*a, b)
    key2 = (sign_cd*c, d)

    if key1 in bad: bad[key1][0] += 1
    elif key2 in bad: bad[key2][1] += 1
    else: bad[key1] = [1,0]

cnt = 1
for a,b in bad:
    c1, c2 = bad[a, b]
    c3 = (2**c1 - 1) % mod
    c3 += (2**c2 - 1) % mod
    c3 += 1
    cnt = cnt * c3 % mod

ans = (cnt + zero - 1 + mod) % mod

# print('cnt',cnt)
# print('zero',zero)
# print('ans',ans)
print(ans)

Submission status: Wrong Answer

Solution code:
from math import gcd
n = int(input())
bad = {}
for i in range(n):
    a,b = map(int, input().split())
    if a != 0 and b != 0:
        g = gcd(a, b)
        a //= g
        b //= g

    is_minus = True
    if a>0 and b>0 : is_minus = False
    if a<0 and b<0 : is_minus = False
    sign_ab = -1 if is_minus else 1
    sign_cd = 1 if is_minus else -1
    d, c = a, b = abs(a), abs(b)
    key1 = (sign_ab*a, b)
    key2 = (sign_cd*c, d)

    # print(f'{key1}  {key2}')

    if key1 in bad: bad[key1][0] += 1
    elif key2 in bad: bad[key2][1] += 1
    else: bad[key1] = [1,0]

# print(n)
# print(bad)
# for a,b in bad:
#     print(f'({a:2}, {b:2}) {bad[a,b]}')

zero = 0
cnt = 1
for a,b in bad:
    # print('a b',a,b)
    if a==0 and b==0:
        pass
        # print('zero',a,b)
        c1, c2 = bad[a, b]
        zero += c1 + c2
    else:
        pass
        # print('none zero',a,b)
        c1, c2 = bad[a, b]
        # print('c1,c2:',c1,c2)
        c3 = (2**c1 - 1) + (2**c2 - 1) + 1
        # print('c3:',c3)
        cnt *= c3

ans = cnt
ans += zero
ans -= 1
# print('cnt',cnt)
# print('zero',zero)
# print('ans',ans)
print(ans)

Submission status: Wrong Answer

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


def select_num(a, b, mod=1000000007):
    sum = pow(2, a, mod) + pow(2, b, mod) - 1
    return sum % mod


def dict_count(d, num):
    d.setdefault(num, 0)
    d[num] += 1


def main():
    MOD = 1000000007
    n = int(input())

    a_div_b = {}
    a0 = b0 = zero = 0
    for i in range(n):
        a, b = map(int, input().split())
        if a == 0 or b == 0:
            if a == b == 0:
                n -= 1
                zero += 1
            elif a == 0:
                a0 += 1
            elif b == 0:
                b0 += 1
            continue

        gcd = math.gcd(a, b)
        a //= gcd
        b //= gcd
        dict_count(a_div_b, a / b)

    ans = 1
    cnt = 0
    while a_div_b:
        cnt += 1
        k_a, v_a = a_div_b.popitem()
        v_b = a_div_b.pop(-1 / k_a, False)
        if v_b:
            ans *= select_num(v_a, v_b, MOD)
            ans %= MOD
            cnt -= 1
            # print(f"{k_a = }, {v_a = }, {v_b = }\n{ans = }")
    else:
        ans *= select_num(a0, b0, MOD)
        ans *= pow(2, cnt, MOD)
        ans += zero - 1
        ans %= MOD

    # print(f"{a_div_b = } \n{b_div_a = }  \n{len(b_div_a) = }")
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

N = int(input())
A = dict()
ngs = 0
zi = 0
for i in range(N):
    a,b = map(int,input().split())
    if a == 0 and b != 0:
        a,b = 0,1
    elif b == 0 and a != 0:
        a,b = 1,0
    elif b == 0 and a == 0:
        zi += 1
    else:
        x = gcd(a,b)
        a = a // x
        b = b // x
        if b < 0:
            a,b = -a,-b
    if (a,b) not in A.keys():
        A[(a,b)] = 1
    else:
        A[(a,b)] += 1
    if (b,-a) in A.keys():
        ngs += A[(b,-a)]
 
 
fac = [1,1]
inv = [1,1]
finv = [1,1]
 
MOD = 100000007
for i in range(2,N+1):
    tmp = fac[-1] * i % MOD
    fac.append(tmp)
    tmp = MOD - inv[MOD % i] * (MOD // i) % MOD
    inv.append(tmp)
    tmp = finv[-1] * inv[i] % MOD
    finv.append(tmp)

ret = 0
N -= zi
# n = 1
ret += N
retlist = [1,N]
for n in range(2,N+1):
    tmp = (fac[N] * finv[n] % MOD) * finv[N-n] % MOD
    retlist.append(tmp)
    ret += tmp - retlist[n-2] * ngs
print(ret)