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 sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
N = int(input())
MOD = 10**9+7
AB = []
x = 0
y = 0
d = defaultdict(int)
ch = defaultdict(int)
flag = 0
for _ in range(N):
    a,b = map(int,input().split())
    if a == 0 and b == 0:
        flag += 1
        continue
    elif a == 0:
        x += 1
        continue
    elif b == 0:
        y += 1
        continue
    else:
        dd = math.gcd(abs(a),abs(b))
        a /= dd
        b /= dd
        if a < 0:
            a *= -1
            b *= -1
        d[(a,b)] += 1
        AB.append([a,b])
n = len(AB)
ans = 1
for i in range(n):
    a,b = AB[i]
    if ch[(a,b)] != 0:
        continue
    m = d[(a,b)]
    if b > 0:
        l = d[(b,(-1)*a)]
        ch[(a,b)] = 1
        ch[(b,(-1)*a)] = 1
    else:
        l = d[((-1)*b,a)]
        ch[(a,b)] = 1
        ch[((-1)*b,a)] = 1
    ans *= (pow(2,m,MOD)+pow(2,l,MOD)-1)%MOD
ans *= (pow(2,x,MOD)+pow(2,y,MOD)-1)%MOD
ans = ans -1 + flag
ans = ans % MOD
print(ans)

Submission status: Wrong Answer

Solution code:
def e_bullet(MOD=10**9 + 7):
    from math import gcd
    from collections import defaultdict
    N = int(input())

    zero_all = 0
    pair = defaultdict(int)
    for _ in range(N):
        a, b = [int(i) for i in input().split()]
        if a == 0 and b == 0:
            zero_all += 1
            continue

        # 既約分数にしておきたい
        g = gcd(a, b)
        pair[(a // g, b // g)] += 1  # 既約分数 a/b とみなす

    done = set()
    total = 1
    for (a, b), v in list(pair.items()):
        if (b, -a) in done or (-b, a) in done:
            continue  # a/b に対応するものがあるかはすでに調べた
        done.add((a, b))

        # a/b に対応する b/(-a) か (-b)/a に注目する
        w = pair[(b, -a)] + pair[(-b, a)]
        # それらを選ぶと仲が悪いので、a/b となるものだけ選ぶか b/(-a) か (-b)/a
        # となるものだけ選ぶか、どちらか一方だけ選択したときに仲が悪くならない
        # これまでの選び方に対して仲が悪くならない選び方を決めるので、total は積を取る
        # ただし、両方とも 1 つも選ばないということはできないため、-1 する
        total *= pow(2, v, MOD) + pow(2, w, MOD) - 1
        total %= MOD

    ans = (total + zero_all - 1) % MOD
    return ans

print(e_bullet())

Submission status: Wrong Answer

Solution code:
#!python3

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

# input
N = int(input())
AB = [LI() for _ in range(N)]

MOD = 10 ** 9 + 7


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


def create_pairs():
    z = 0
    d = {}
    for a, b in AB:
        # irre
        if a == 0 and b == 0:
            z += 1
            continue
        if a == 0:
            b = 1
        elif b == 0:
            a == 1
        else:
            m = abs(gcd(a, b))
            a, b = a // m, b // m
        
        # 180
        if b < 0:
            a, b = -a, -b

        if a > 0:
            t = (a, b)
            i = 0
        else:
            t = (b, -a)
            i = 1
        if t in d:
            d[t][i] += 1
        else:
            d[t] = [0, 0]
            d[t][i] = 1
    
    return d, z


def main():
    p2 = [None] * (N + 1)
    p2[0] = 1
    for i in range(1, N + 1):
        p2[i] = p2[i - 1] * 2 % MOD
    
    d, z = create_pairs()
    ans = 1
    for x, y in d.values():
        v = p2[x] + p2[y] - 1
        ans = ans * v % MOD

    ans += z - 1
    print(ans)
    

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
import math
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict

MOD = 10**9+7
N = int(input())
dic = defaultdict(int)
zero = 0
left_zero = 0
right_zero = 0
for i in range(N):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zero += 1
    elif a == 0:
        left_zero += 1
    elif b == 0:
        right_zero += 1
    else:
        g = math.gcd(a, b)
        a //= g
        b //= g
        dic[a,b] += 1
done = set()
ans = 1
for a,b in dic:
    k = (a, b)
    if k in done: continue
    rk = (-b, a)
    rk2 = (b, -a)
    done.add(k)
    done.add(rk)
    done.add(rk2)
    c = pow(2, dic[k], MOD)-1
    if rk in dic:
        c += pow(2, dic[rk], MOD)-1
    if rk2 in dic:
        c += pow(2, dic[rk2], MOD)-1
    c += 1
    ans *= c
    ans %= MOD
c1 = pow(2, left_zero, MOD)-1
c2 = pow(2, right_zero, MOD)-1
c = c1+c2+1
ans *= c
ans += zero
print((ans-1)%MOD)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
N = int(input())
MOD = 10**9+7
AB = []
x = 0
y = 0
d = defaultdict(int)
ch = defaultdict(int)
flag = 0
for _ in range(N):
    a,b = map(int,input().split())
    if a == 0 and b == 0:
        flag += 1
        continue
    elif a == 0:
        x += 1
        continue
    elif b == 0:
        y += 1
        continue
    else:
        dd = math.gcd(abs(a),abs(b))
        a /= dd
        b /= dd
        if a < 0:
            a *= -1
            b *= -1
        d[(a,b)] += 1
        AB.append([a,b])
n = len(AB)
ans = 1
for i in range(n):
    a,b = AB[i]
    if ch[(a,b)] != 0:
        continue
    m = d[(a,b)]
    if b > 0:
        l = d[(b,(-1)*a)]
        ch[(a,b)] = 1
        ch[(b,(-1)*a)] = 1
    else:
        l = d[((-1)*b,a)]
        ch[(a,b)] = 1
        ch[((-1)*b,a)] = 1
    ans *= (pow(2,m,MOD)+pow(2,l,MOD)-1)
ans *= (pow(2,x,MOD)+pow(2,y,MOD)-1)
ans = ans -1 + flag
ans = ans % MOD
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import Counter

mod = 1000000007
 
N = int(sys.stdin.readline().strip())
fishes = []
for _ in range(N):
    a, b = map(int, sys.stdin.readline().strip().split())
    # 角度だけが重要なので座標圧縮して良い
    if a == 0 and b == 0:
        fishes.append((0, 0))
    elif a == 0:
        fishes.append((0, 1))
    elif b == 0:
        fishes.append((1, 0))
    else:
        gcd = math.gcd(a, b)
        fishes.append((a // gcd, b // gcd))

# print(fishes)

# (a, b)ごとにカウント
counter = Counter(fishes)
# print(counter)

calculated = set()
ans = 1
# 組み合わせを計算
for ((a, b), count) in counter.items():
    if a == 0 or b == 0:
        continue
    # 計算済みの場合
    if (a, b) in calculated:
        continue

    # 仲が悪いイワシの数
    bad_count = 0
    # 90度異なるものがダメ
    for (a_k, b_k) in ((-1, 1), (1, -1)):
        bad_pair = (b * a_k, a * b_k)
        if bad_pair in counter:
            bad_count += counter[bad_pair]
            calculated.add(bad_pair)

    # 仲が悪いイワシがいない場合
    if bad_count == 0:
        ans *= 2**count
        ans %= mod
    else:
        # 仲が良いものだけの組み合わせ
        good = 2**count
        
        # 仲が悪いものだけの組み合わせ
        bad = 2**bad_count

        # 全て選ばない場合は許容しないので1を引いておく
        ans *= good + bad - 1
        ans %= mod

if (1,0) not in counter:
    counter[(1,0)] = 0
if (0,1) not in counter:
    counter[(0,1)] = 0
if (0,0) not in counter:
    counter[(0,0)] = 0
ans *= 2**counter[(1, 0)] + 2**counter[(0, 1)] - 1
ans %= mod

ans += counter[(0, 0)]
# 全部選ばないものは駄目
ans -= 1
ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
#!python3

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

# input
N = int(input())
AB = [LI() for _ in range(N)]

MOD = 10 ** 9 + 7


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


def create_pairs():
    d = {}
    for a, b in AB:
        # irre
        if a == 0 and b == 0:
            continue
        if a == 0:
            b = 1
        elif b == 0:
            a == 1
        else:
            m = abs(gcd(a, b))
            a, b = a // m, b // m
        
        # 180
        if b < 0:
            a, b = -a, -b

        if a > 0:
            t = (a, b)
            i = 0
        else:
            t = (b, -a)
            i = 1
        if t in d:
            d[t][i] += 1
        else:
            d[t] = [0, 0]
            d[t][i] = 1
    
    return d


def main():
    p2 = [None] * (N + 1)
    p2[0] = 1
    for i in range(1, N + 1):
        p2[i] = p2[i - 1] * 2 % MOD
    
    d = create_pairs()
    ans = 1
    for x, y in d.values():
        v = p2[x] + p2[y] - 1
        ans = ans * v % MOD

    ans -= 1        
    print(ans)
    

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()


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

mod=10**9+7
idle_max=10**19


for i in range(N):
    a,b=AB[i]
    if a and b:
        n=gcd(a,b)
        if a<0 and n>0 or a>0 and n<0:
            n*=-1
        AB[i][0]//=n
        AB[i][1]//=n
data=defaultdict(int)
c=0
M=0
Z=1
twofac=[1]
for i in range(N+1):
    twofac.append(twofac[-1]*2%mod)
twoifac=[pow(i,mod-2,mod) for i in twofac]
for i in range(N):
    a,b=AB[i]
    P=Z
    flag=1
    if a==0 and b==0:
        continue
    elif a and b==0:
        x=data[-a]
        if x:
            P*=twoifac[x]
    elif a==0 and b:
        x=data[-b*idle_max]
        if x:
            P*=twoifac[x]
    else:
        x=data[-b*idle_max+a]
        if x:
            P*=twoifac[x]
        x=data[b*idle_max-a]
        if x:
            P*=twoifac[x]
    #print(Z,P)
    P%=mod
    c+=P
    c%=mod
    Z+=P
    Z%=mod
    data[a*idle_max+b]+=1

print(c)

Submission status: Wrong Answer

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()


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

mod=10**9+7
idle_max=10**19


for i in range(N):
    a,b=AB[i]
    if a and b:
        n=gcd(a,b)
        if a<0 and n>0 or a>0 and n<0:
            n*=-1
        AB[i][0]//=n
        AB[i][1]//=n
data=defaultdict(int)
c=0
M=0
Z=1
twofac=[1]
for i in range(N+1):
    twofac.append(twofac[-1]*2%mod)
twoifac=[pow(i,mod-2,mod) for i in twofac]

for i in range(N):
    a,b=AB[i]
    P=Z
    flag=1
    if a==0 and b==0:
        continue
    elif a and b==0:
        x=data[-a]
        if x:
            P*=twofac[x]
    elif a==0 and b:
        x=data[-b*idle_max]
        if x:
            P*=twofac[x]
    else:
        x=data[-b*idle_max+a]
        if x:
            P*=twofac[x]
        x=data[b*idle_max-a]
        if x:
            P*=twofac[x]
    #print(Z,P)
    P%=mod
    c+=P
    c%=mod
    Z+=P
    Z%=mod
    data[a*idle_max+b]+=1

print(c)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))
from fractions import Fraction

N = ii()
ab = li2(N)
mod = 10**9+7

d = defaultdict(int)
for i in range(N):
    if ab[i][1] != 0:
        d[Fraction(ab[i][0], ab[i][1])] += 1
    elif ab[i][0] == ab[i][1] == 0:
        d[10**18+2] += 1
    else:
        d[10**18+1] += 1
d_l = sorted(d.items(), key=lambda x:x[0])

cnt = 1
flag = 0
for k, v in d_l:
    if k == 10**18+2:
        flag = v
        continue
    if k == 0:
        if d[10**18+1]:
            cnt = (cnt * ((2**v-1) + (2**d[10**18+1]-1) + 1)) % mod
        else:
            cnt = ((v+1) * cnt) % mod
    elif k == 10**18+1:
        if d[0.0]:
            continue
        cnt = ((v+1) * cnt) % mod
    elif k > 0:
        if not d[Fraction(-1, k)]:
            cnt = ((v+1) * cnt) % mod
    elif d[Fraction(-1, k)]:
        cnt = (cnt * ((2**v-1) + (2**d[Fraction(-1, k)]-1) + 1)) % mod
    else:
        cnt = ((v+1) * cnt) % mod

print((cnt - 1 + flag) % mod)

Submission status: Wrong Answer

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()


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

mod=10**9+7
idle_max=10**19


for i in range(N):
    a,b=AB[i]
    if a and b:
        n=gcd(a,b)
        if a<0 and n>0 or a>0 and n<0:
            n*=-1
        AB[i][0]//=n
        AB[i][1]//=n
data=defaultdict(int)
c=0
M=0
Z=1
for i in range(N):
    a,b=AB[i]
    P=Z
    flag=1
    if a==0 and b==0:
        continue
    elif a and b==0:
        x=data[-a]
        if x:
            P*=pow(pow(2,x,mod),mod-2,mod)
    elif a==0 and b:
        x=data[-b*idle_max]
        if x:
            P*=pow(pow(2,x,mod),mod-2,mod)
    else:
        x=data[-b*idle_max+a]
        if x:
            P*=pow(pow(2,x,mod),mod-2,mod)
        x=data[b*idle_max-a]
        if x:
            P*=pow(pow(2,x,mod),mod-2,mod)
    #print(Z,P)
    c+=P
    c%=mod
    Z+=P
    data[a*idle_max+b]+=1

print(c)

Submission status: Wrong Answer

Solution code:
import math
import numpy as np
import queue
from collections import deque
import heapq
mod = 10**9+7
ans = 1
iw0 = 0

def twoxxn(t,mod):
    ni = t
    an = 1
    n2 = 2
    while ni > 0:
        if ni%2 == 1:
            an = (an*n2)%mod
        n2 = (n2**2)%mod
        ni >>= 1
    return an

n = int(input())
d = dict()
for i in range(n):
    a,b = map(int,input().split())
    if a == 0 and b == 0:
        iw0 += 1
        continue
    if a == 0:
        b = 1
        g = 1
    elif b == 0:
        a = 1
        g = 1
    else:
        g = math.gcd(abs(a),abs(b))
    if a < 0 :
        a = -a
        b = -b
    p1 = a//g, b//g
    if p1 in d:
        d[p1] += 1
    else:
        d[p1] = 1

for (i0, i1) in d.keys():
    din = d[(i0,i1)]
    if din == -1:
        continue
    if i1 < 0:
        i00 = -i0
        i10 = -i1
    else:
        i00 = i0
        i10 = i1
    if (i10,-i00) in d.keys():
        aaa = (twoxxn(d[(i10,-i00)],mod)+twoxxn(din,mod)-1)%mod
        ans = (ans*aaa)%mod
        d[(i10,-i00)] = -1
    else:
        ans = (ans*twoxxn(din,mod))%mod

if len(d.keys()) == 0:
    print(iw0)
    exit()

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

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import Counter

mod = 1000000007
 
N = int(sys.stdin.readline().strip())
fishes = []
for _ in range(N):
    a, b = map(int, sys.stdin.readline().strip().split())
    # 角度だけが重要なので座標圧縮して良い
    if a == 0 and b == 0:
        fishes.append((0, 0))
    if a == 0:
        fishes.append((0, 1))
    elif b == 0:
        fishes.append((1, 0))
    else:
        gcd = math.gcd(a, b)
        fishes.append((a // gcd, b // gcd))

# print(fishes)

# (a, b)ごとにカウント
counter = Counter(fishes)
# print(counter)

calculated = set()
ans = 1
# 組み合わせを計算
for ((a, b), count) in counter.items():
    if a == 0 or b == 0:
        continue
    # 計算済みの場合
    if (a, b) in calculated:
        continue

    # 仲が悪いイワシの数
    bad_count = 0
    # 90度異なるものがダメ
    for (a_k, b_k) in ((-1, 1), (1, -1)):
        bad_pair = (b * a_k, a * b_k)
        if bad_pair in counter:
            bad_count += counter[bad_pair]
            calculated.add(bad_pair)

    # 仲が悪いイワシがいない場合
    if bad_count == 0:
        ans *= 2**count
        ans %= mod
    else:
        # 仲が良いものだけの組み合わせ
        good = 2**count
        
        # 仲が悪いものだけの組み合わせ
        bad = 2**bad_count

        # 全て選ばない場合は許容しないので1を引いておく
        ans *= good + bad - 1
        ans %= mod

if (1,0) not in counter:
    counter[(1,0)] = 0
if (0,1) not in counter:
    counter[(0,1)] = 0
ans *= 2**counter[(1, 0)] + 2**counter[(0, 1)] - 1
ans %= mod

ans += counter[(0, 0)]
ans %= mod

# 全部選ばないものは駄目
ans -= 1
ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
import math
import numpy as np
import queue
from collections import deque
import heapq
mod = 10**9+7
ans = 1
iw0 = 0

def twoxxn(t,mod):
    ni = t
    an = 1
    n2 = 2
    while ni > 0:
        if ni%2 == 1:
            an = (an*n2)%mod
        n2 = (n2**2)%mod
        ni >>= 1
    return an

n = int(input())
d = dict()
for i in range(n):
    a,b = map(int,input().split())
    if a == 0 and b == 0:
        iw0 += 1
        continue
    if a == 0:
        b = 1
        g = 1
    elif b == 0:
        a = 1
        g = 1
    else:
        g = math.gcd(abs(a),abs(b))
    if a < 0 :
        a = -a
        b = -b
    p1 = a//g, b//g
    if p1 in d:
        d[p1] += 1
    else:
        d[p1] = 1

for (i0, i1) in d.keys():
    din = d[(i0,i1)]
    if din == -1:
        continue
    if i1 < 0:
        i00 = -i0
        i10 = -i1
    else:
        i00 = i0
        i10 = i1
    if (i10,-i00) in d.keys():
        aaa = (twoxxn(d[(i10,-i00)],mod)+twoxxn(din,mod)-1)%mod
        print(aaa)
        ans = (ans*aaa)%mod
        d[(i10,-i00)] = -1
    else:
        ans = (ans*twoxxn(din,mod))%mod

if len(d.keys()) == 0:
    print(iw0)
    exit()

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

Submission status: Wrong Answer

Solution code:
import math
import numpy as np
import queue
from collections import deque
import heapq
mod = 10**9+7
ans = 1
i0 = 0

def twoxxn(t,mod):
    ni = t
    an = 1
    n2 = 2
    while ni > 0:
        if ni%2 == 1:
            an = (an*n2)%mod
        n2 = (n2**2)%mod
        ni >>= 1
    return an

n = int(input())
d = dict()
for i in range(n):
    a,b = map(int,input().split())
    if a == 0 and b == 0:
        i0 += 1
        continue
    if a == 0:
        b = 1
        g = 1
    elif b == 0:
        a = 1
        g = 1
    else:
        g = math.gcd(abs(a),abs(b))
    if a < 0 :
        a = -a
        b = -b
    p1 = a//g, b//g
    if p1 in d:
        d[p1] += 1
    else:
        d[p1] = 1

for (i0, i1) in d.keys():
    din = d[(i0,i1)]
    if din == -1:
        continue
    if i1 < 0:
        i00 = -i0
        i10 = -i1
    else:
        i00 = i0
        i10 = i1
    if (i10,-i00) in d.keys():
        aaa = (twoxxn(d[(i10,-i00)],mod)+twoxxn(din,mod)-1)%mod
        print(aaa)
        ans = (ans*aaa)%mod
        d[(i10,-i00)] = -1
    else:
        ans = (ans*twoxxn(din,mod))%mod

if len(d.keys()) == 0:
    print(i0)
    exit()

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N = ii()
ab = li2(N)
mod = 10**9+7

d = defaultdict(int)
for i in range(N):
    if ab[i][1] != 0:
        d[ab[i][0] / ab[i][1]] += 1
    elif ab[i][0] == ab[i][1] == 0:
        d[10**18+2] += 1
    else:
        d[10**18+1] += 1
d_l = sorted(d.items(), key=lambda x:x[0])

cnt = 1
flag = 0
for k, v in d_l:
    if k == 10**18+2:
        flag = v
        continue
    if k == 0:
        if d[10**18+1]:
            cnt = (cnt * ((2**v-1) + (2**d[10**18+1]-1) + 1)) % mod
        else:
            cnt = ((v+1) * cnt) % mod
    elif k == 10**18+1:
        if d[0.0]:
            continue
        cnt = ((v+1) * cnt) % mod
    elif k > 0:
        if not d[-1/k]:
            cnt = ((v+1) * cnt) % mod
    elif d[-1/k]:
        cnt = (cnt * ((2**v-1) + (2**d[-1/k]-1) + 1)) % mod
    else:
        cnt = ((v+1) * cnt) % mod

print((cnt - 1 + flag) % mod)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import Counter

mod = 1000000007
 
N = int(sys.stdin.readline().strip())
fishes = []
for _ in range(N):
    a, b = map(int, sys.stdin.readline().strip().split())
    # 角度だけが重要なので座標圧縮して良い
    if a == 0 and b == 0:
        fishes.append((0, 0))
    if a == 0:
        fishes.append((0, 1))
    elif b == 0:
        fishes.append((1, 0))
    else:
        gcd = math.gcd(a, b)
        fishes.append((a // gcd, b // gcd))

# print(fishes)

# (a, b)ごとにカウント
counter = Counter(fishes)
# print(counter)

calculated = set()
ans = 1
# 組み合わせを計算
for ((a, b), count) in counter.items():
    if (a, b) == (0, 0):
        continue
    # 計算済みの場合
    if (a, b) in calculated:
        continue

    # 仲が悪いイワシの数
    bad_count = 0
    # 90度異なるものがダメ
    for (a_k, b_k) in ((-1, 1), (1, -1)):
        bad_pair = (b * a_k, a * b_k)
        if bad_pair in counter:
            bad_count += counter[bad_pair]
            calculated.add(bad_pair)

    # 仲が悪いイワシがいない場合
    if bad_count == 0:
        ans *= 2**count
        ans %= mod
    else:
        # 仲が良いものだけの組み合わせ
        good = 2**count
        
        # 仲が悪いものだけの組み合わせ
        bad = 2**bad_count

        # 全て選ばない場合は許容しないので1を引いておく
        ans *= good + bad - 1
        ans %= mod

ans += counter[(0, 0)]
ans %= mod
ans -= 1
ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
from math import gcd

n = int(input())
MOD = 10**9+7
p_map = {}
n_map = {}

p_zero_map = 0
n_zero_map = 0
z_map = 0
for _ in range(n):
    ab = list(map(int, input().split()))
    ab_gcd = gcd(ab[0], ab[1])
    if ab_gcd == 0:
        ab_gcd = 1
    a = ab[0]//ab_gcd
    b = ab[1]//ab_gcd

    if (a > 0 and b > 0) or (a < 0 and b < 0):
        if a < 0:
            a = -a
            b = -b
        key = "{}_{}".format(a, b)
        if key not in p_map:
            p_map[key] = 1
        else:
            p_map[key] += 1
    elif a == 0 and b == 0:
        z_map += 1
    elif a == 0 and b != 0:
        n_zero_map += 1
    elif b == 0 and a != 0:
        p_zero_map += 1
    else:
        if b < 0:
            a = -a
            b = -b
        key = "{}_{}".format(a, b)
        if key not in n_map:
            n_map[key] = 1
        else:
            n_map[key] += 1

ans = 1
for k, v in p_map.items():
    a = int(k.split("_")[0])
    b = int(k.split("_")[1])
    n_num = 0
    key_a = "{}_{}".format(-b, a)
    if key_a in n_map:
        n_num += n_map.pop(key_a)
    res = 0
    res += pow(2, v, MOD)-1
    if n_num > 0:
        res += pow(2, n_num, MOD)-1
    res += 1
    ans *= res
    ans %= MOD

n_num = sum(n_map.values())
if n_num > 0:
    ans *= pow(2, n_num, MOD)
    ans %= MOD

res = 0
if p_zero_map > 0 and n_zero_map > 0:
    res = pow(2, p_zero_map, MOD)-1 + pow(2, n_zero_map, MOD)-1
    res += 1
    res %= MOD
elif p_zero_map > 0 and n_zero_map == 0:
    res = pow(2, p_zero_map, MOD)
elif p_zero_map == 0 and n_zero_map > 0:
    res = pow(2, n_zero_map, MOD)
if res > 0:
    ans *= res
    ans %= MOD


if z_map > 0:
    ans += z_map
ans %= MOD
ans -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
import sys

# sys.stdout.write(str(n)+"\n")
MODULO = 1000000007
INF = 1e18+10

n = int(input())
a = [0 for i in range(n)]
b = [0 for i in range(n)]

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

graph = [[] for _ in range(n)]
value_indices = {} # a_b values
zeroes = 0
used = [False for _ in range(n)]
for i in range(n):
	if a[i] == 0 and b[i] == 0:
		zeroes += 1
		used[i] = True
		# for j in range(n):
		# 	graph[i].append(j)
		# 	graph[j].append(i)
	else:
		if a[i] == 0:
			a_b = 0
			m_b_a = INF
		elif b[i] == 0:
			a_b = INF
			m_b_a = 0
		else:
			a_b = a[i] / b[i]
			m_b_a = -b[i] / a[i]

		if m_b_a in value_indices:
			for j in value_indices[m_b_a]:
				graph[i].append(j)
				graph[j].append(i)
		value_indices[a_b] = value_indices.get(a_b, []) + [i]

# print("value_indices", value_indices)
# print("graph", graph)

def comb(i):
	# print("comb", i)
	layers = [[i], []]
	used[i] = True

	chet = 0
	nechet = 0
	is_chet = True
	cur_layer_ind = 0
	next_layer_ind = 1

	while len(layers[cur_layer_ind]) > 0:
		if is_chet:
			cur_layer_ind = 0
			next_layer_ind = 1
			chet += len(layers[cur_layer_ind])
		else:
			cur_layer_ind = 1
			next_layer_ind = 0
			nechet += len(layers[cur_layer_ind])
		is_chet = not is_chet
		# layers.append(cur_layer)
		layers[next_layer_ind] = []
		for item in layers[cur_layer_ind]:
			for child in graph[item]:
				if not used[child]:
					layers[next_layer_ind].append(child)
					used[child] = True
		# cur_layer = next_layer.copy()
	# including empty
	return 1*pow(2, chet, MODULO) + 1*pow(2, nechet, MODULO) -1


ans = 1
for i in range(n):
	if not used[i]:
		if len(graph[i]) == 0:
			used[i] = True
			ans *= 2
			ans %= MODULO
		else:
			ans *= comb(i)
			ans %= MODULO

# -1 is for empty
print((ans-1+zeroes) % MODULO)

Submission status: Wrong Answer

Solution code:
from math import gcd

n = int(input())
MOD = 10**9+7
p_map = {}
n_map = {}

p_zero_map = 0
n_zero_map = 0
z_map = 0
for _ in range(n):
    ab = list(map(int, input().split()))
    ab_gcd = gcd(ab[0], ab[1])
    if ab_gcd == 0:
        ab_gcd = 1
    a = ab[0]//ab_gcd
    b = ab[1]//ab_gcd

    if (a > 0 and b > 0) or (a < 0 and b < 0):
        if a < 0:
            a = -a
            b = -b
        key = "{}_{}".format(a, b)
        if key not in p_map:
            p_map[key] = 1
        else:
            p_map[key] += 1
    elif a == 0 and b == 0:
        z_map += 1
    elif a == 0 and b != 0:
        n_zero_map += 1
    elif b == 0 and a != 0:
        p_zero_map += 1
    else:
        if b < 0:
            a = -a
            b = -b
        key = "{}_{}".format(a, b)
        if key not in n_map:
            n_map[key] = 1
        else:
            n_map[key] += 1

ans = 1
for k, v in p_map.items():

    a = int(k.split("_")[0])
    b = int(k.split("_")[1])
    n_num = 0
    key_a = "{}_{}".format(-b, a)
    if key_a in n_map:
        n_num += n_map.pop(key_a)
    res = 0
    res += pow(2, v, MOD)-1
    if n_num > 0:
        res += pow(2, n_num, MOD)-1
    res += 1
    ans *= res
    ans %= MOD

n_num = sum(n_map.values())
ans *= pow(2, n_num, MOD)
ans %= MOD

res = 0
if p_zero_map > 0 and n_zero_map > 0:
    res = pow(2, p_zero_map, MOD)-1 + pow(2, n_zero_map, MOD)-1
    res += 1
    res %= MOD
elif p_zero_map > 0 and n_zero_map == 0:
    res = pow(2, p_zero_map, MOD)
elif p_zero_map == 0 and n_zero_map > 0:
    res = pow(2, n_zero_map, MOD)
if res > 0:
    ans *= res
    ans %= MOD


if z_map > 0:
    ans += z_map
ans %= MOD
ans -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N = ii()
ab = li2(N)
mod = 10**9+7

d = defaultdict(int)
for i in range(N):
    if ab[i][1] != 0:
        d[ab[i][0] / ab[i][1]] += 1
    elif ab[i][0] == ab[i][1] == 0:
        d[10**18+2] += 1
    else:
        d[10**18+1] += 1
d_l = sorted(d.items(), key=lambda x:x[0])

cnt = 1
flag = 0
for k, v in d_l:
    if k == 10**18+2:
        flag = v
        continue
    if k == 0:
        if d[10**18+1]:
            cnt = (cnt * ((2**v-1) + (2**d[10**18+1]-1) + 1)) % mod
        else:
            cnt = ((v+1) * cnt) % mod
    elif k == 10**18+1:
        if d[0.0]:
            continue
        cnt = ((v+1) * cnt) % mod
    elif k > 0:
        if not d[-1/k]:
            cnt = ((v+1) * cnt) % mod
    elif d[-1/k]:
        cnt = (cnt * ((2**v-1) + (2**d[-1/k]-1) + 1)) % mod
    else:
        cnt = ((v+1) * cnt) % mod

print((cnt - 1 + flag) % mod)