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:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
import bisect
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def Yes(): print("Yes"); return
def No(): print("No"); return

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#############
# Main Code #
#############

N = inputI()
F = []
zero_v = 0
inf = 0
zero = 0
for _ in range(N):
  x,y = inputIL()
  if x==0 and y==0:
    zero_v += 1
  elif x==0:
    inf += 1
  elif y==0:
    zero += 1
  else:
    F.append(y/x)

import collections
c = collections.Counter(F)

keys = [k for k in c]
inv_keys = [-1/k for k in c]

all_keys = list(filter(lambda x: x >0,list(set(keys) | set(inv_keys))))

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

for f in F:
  if f>0:
    all_dic[f][0] += 1
  else:
    all_dic[-1/f][1] += 1



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

for k in all_keys:
  P,N = all_dic[k]

  ans *= (pow(2,P,MOD)) + (pow(2,N,MOD))-1
  ans %= MOD


ans += zero_v-1

print(ans%MOD)

Submission status: Wrong Answer

Solution code:
from math import gcd


MOD = 10**9 + 7

n = int(input())

cnt = {}

zero_cnt = 0
for i in range(n):
    a, b = map(int, input().split())
    if (a,b) == (0,0):
        zero_cnt += 1
        continue
    g = gcd(abs(a), abs(b))
    a /= g
    b /= g
    rotate = 0
    while not (a >= 0 and b > 0):
        a,b = -b,a
        rotate += 1
    if (a,b) not in cnt:
        cnt[(a,b)] = [0,0]

    cnt[(a,b)][rotate % 2] += 1

ans = 1
    
for key in cnt:
    A, B = cnt[key]
    ans *= 1 + pow(2, A, MOD) - 1 + pow(2, B, MOD - 1) - 1
    ans %= MOD

ans += zero_cnt
ans -= 1
print(ans % MOD)

Submission status: Wrong Answer

Solution code:
from math import gcd
n = int(input())
plus = {}
minus = {}
mod = 10**9 + 7
gen = pow(10,19)
zero = 0 # 両方
for i in range(n):
    a,b = map(int,input().split())
    if a == b == 0:
        zero += 1
        continue
    if a < 0:a,b = -a,-b
    g = gcd(a,b)
    a //= g
    b //= g
    key = a*gen + b
    if b > 0:
        if key not in plus.keys():plus[key] = 0
        plus[key] += 1
    else:
        if key not in minus.keys():minus[key] = 0
        minus[key] += 1
ans = pow(2,n-zero,mod)
for k,v in plus.items():
    a = k//gen
    b = k%gen
    opo = b*gen - a
    if opo in minus.keys():
        o = minus[opo]
        ans = ans*pow(2,v*(mod-2)%(mod-1),mod) + ans*pow(2,o*(mod-2)%(mod-1),mod) - ans*pow(2,(v+o)*(mod-2)%(mod-1),mod)
        ans %= mod
print((ans + zero - 1)%mod)

Submission status: Wrong Answer

Solution code:
import sys

int1 = lambda x: int(x) - 1
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 LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

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

def main():
    md=1000000007
    n=II()
    cnt={}
    zero=0
    for _ in range(n):
        a,b=MI()
        if a*b==0:
            zero+=1
            continue
        par=a*b>0
        a=abs(a)
        b=abs(b)
        g=gcd(a,b)
        a//=g
        b//=g
        if par:
            cnt.setdefault((a,b),[0,0])
            cnt[(a,b)][1]+=1
        else:
            cnt.setdefault((b,a),[0,0])
            cnt[(b,a)][0]+=1
    #print(cnt)
    ans=1
    for x,y in cnt.values():
        cur=pow(2,x,md)+pow(2,y,md)-1
        ans=ans*cur%md
    if zero:ans=ans*2%md
    ans=(ans-1)%md
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
from math import gcd


MOD = 10**9 + 7

n = int(input())

cnt = {}

zero_cnt = 0
for i in range(n):
    a, b = map(int, input().split())
    if (a,b) == (0,0):
        zero_cnt += 1
        continue
    g = gcd(abs(a), abs(b))
    a /= g
    b /= g
    rotate = 0
    while not (a > 0 and b > 0):
        a,b = -b,a
        rotate += 1
    if (a,b) not in cnt:
        cnt[(a,b)] = [0,0]

    cnt[(a,b)][rotate % 2] += 1

ans = 1
    
for key in cnt:
    A, B = cnt[key]
    ans *= 1 + pow(2, A, MOD) - 1 + pow(2, B, MOD - 1) - 1
    ans %= MOD

ans += zero_cnt
ans -= 1
print(ans % MOD)

Submission status: Wrong Answer

Solution code:
from math import gcd
n = int(input())
plus = {}
minus = {}
mod = 10**9 + 7
gen = pow(10,19)
zero = 0 # 両方
for i in range(n):
    a,b = map(int,input().split())
    if a == b == 0:
        zero += 1
        continue
    if a < 0:a,b = -a,-b
    g = gcd(a,b)
    a //= g
    b //= g
    key = a*gen + b
    if b > 0:
        if key not in plus.keys():plus[key] = 0
        plus[key] += 1
    else:
        if key not in minus.keys():minus[key] = 0
        minus[key] += 1
ans = pow(2,n-zero,mod)
for k,v in plus.items():
    a = k//gen
    b = k%gen
    opo = b*gen - a
    if opo in minus.keys():
        o = minus[opo]
        ans = ans*pow(2,v*(mod-2)%(mod-1),mod) + ans*pow(2,o*(mod-2)%(mod-1),mod) - ans*pow(2,(v+o)*(mod-2)%(mod-1),mod)
        ans %= mod
print(ans + zero - 1)

Submission status: Wrong Answer

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

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

MOD = 1000000007  # type: int


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

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

    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:
mod = 1000000007
from collections import defaultdict
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

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

ans = 1
for a,b in d1:
    if a==0 and b==0:
        continue
    x = d1[(a,b)]
    y = d2[(b,-a)]
    ans *= pow(2,x,mod)+pow(2,y,mod)-1
    ans %= mod
ans -= 1
ans += d1[(0,0)]
print(ans)

Submission status: Wrong Answer

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

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

MOD = 1000000007  # type: int


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

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

    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
mod = 1000000007

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

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

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[]
B=[]
for i in range(N):
  ab=list(map(int,input().split()))
  A.append(ab[0])
  B.append(ab[1])

S=[]
for i in range(N):
  s=1
  for j in range(i+1,N):
    if A[i]*A[j]+B[i]*B[j]!=0:
      s=s*2
  S.append(s)
  
print(sum(S)%1000000007)

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:
        if ai:
            iw[i][0]=1
        elif bi:
            iw[i][1]=1
    if bi<0:
        iw[i][0]*=-1;iw[i][1]*=-1
    if bi==0 and ai<0:
        iw[i][0]*=-1
iw = [tuple(iwi) for iwi in iw]
C=Counter(iw)
ans=1
mod=10**9+7
#print(C)
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
        elif C[(ai,bi)]>0:
            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
        elif C[(ai,bi)]>0:
            ans*= pow(2,C[(ai,bi)],mod)
            ans%=mod
    
    #print((ai,bi),C[(ai,bi)],ans)
print(ans-1)

Submission status: Wrong Answer

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    from math import gcd
    input = sys.stdin.buffer.readline

    N = int(input())
    cnt = {}
    zz = 0
    for _ in range(N):
        a, b = map(int, input().split())
        if a == b == 0:
            zz += 1
            continue
        if a < 0:
            a = -a
            b = -b
        g = gcd(abs(a), abs(b))
        x = (a // g, b // g)
        if x in cnt:
            cnt[x] += 1
        else:
            cnt[x] = 1

    ans = 1
    num = 0
    for x in cnt:
        if cnt[x] == 0:
            continue
        a, b = x
        if b > 0:
            y = (b, -a)
        else:
            y = (-b, a)
        if y in cnt:
            nx = cnt[x]
            ny = cnt[y]
            cnt[y] = 0
            ans = (ans * ((pow(2, nx, mod) - 1) + (pow(2, ny, mod) - 1) + 1)%mod)%mod
        else:
            num += cnt[x]
    ans = (ans * pow(2, num, mod))%mod
    ans = (ans - 1)%mod
    print((ans + zz)%mod)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    from math import gcd
    input = sys.stdin.buffer.readline

    N = int(input())
    cnt = {}
    zz = 0
    for _ in range(N):
        a, b = map(int, input().split())
        if a == b == 0:
            zz += 1
            continue
        if a < 0:
            a = -a
            b = -b
        g = gcd(abs(a), abs(b))
        x = (a // g, b // g)
        if x in cnt:
            cnt[x] += 1
        else:
            cnt[x] = 1

    ans = 1
    num = 0
    for x in cnt:
        if cnt[x] == 0:
            continue
        a, b = x
        if b > 0:
            y = (b, -a)
        else:
            y = (-b, a)
        if y in cnt:
            nx = cnt[x]
            ny = cnt[y]
            cnt[y] = 0
            ans = (ans * ((pow(2, nx, mod) - 1) + (pow(2, ny, mod) - 1) + 1)%mod)%mod
        else:
            num += cnt[x]
    ans = (ans * pow(2, num, mod))%mod
    ans = (ans - 1)%mod
    print(ans + zz)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from math import gcd
import sys

input=sys.stdin.readline

N=int(input())
dicplus={}
dicminus={}
dicinf=0
diczero=0
dicnan=0
for i in range(N):
    a,b=map(int,input().split())
    g=gcd(a,b)
    if g==0:
        dicnan+=1
    else:
        A=a//g
        B=b//g
        if A*B>0:
            A=abs(A)
            B=abs(B)
            if (A,B) not in dicplus:
                dicplus[(A,B)]=0
            dicplus[(A,B)]+=1
        elif A*B<0:
            A=abs(A)
            B=abs(B)
            if (A,B) not in dicminus:
                dicminus[(A,B)]=0
            dicminus[(A,B)]+=1
        elif A!=0:
            dicinf+=1
        elif B!=0:
            diczero+=1


ans=1
mod=10**9+7
for a,b in dicplus:
    if (b,a) in dicminus:
        ans*=(pow(2,dicplus[(a,b)],mod)-1+pow(2,dicminus[(b,a)],mod)-1+1)
        ans%=mod
    else:
        ans*=pow(2,dicplus[(a,b)],mod)
        ans%=mod

for a,b in dicminus:
    if (b,a) not in dicplus:
        ans*=pow(2,dicminus[(a,b)],mod)
        ans%=mod

ans*=(pow(2,dicinf,mod)-1+pow(2,diczero,mod)-1+1)
ans%=mod

print(ans-1+dicnan)

Submission status: Wrong Answer

Solution code:
import numpy as np
import itertools

n = int(input())
x = np.zeros((n, 2))
for i in range(n):
    _tmp = input()
    x[i, 0], x[i, 1] = [float(f) for f in _tmp.split(" ")]

counter = n
for i, j in itertools.combinations(np.arange(n), 2):
    res = x[i, 0] * x[j, 0] + x[i, 1] * x[j, 1]
    if res != 0:
        counter += 1

print(counter % 1000000007)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read


n,*ab = [int(i) for i in read().split()]

M = iter(ab)
d = {}

from math import gcd
for a,b in zip(M,M):
    if a==b==0: continue
    g = gcd(a,b)
    a//=g
    b//=g
    if b < 0:
        a = -a
        b = -b
    if b==0 and a == -1:
        a = 1
    
    if a > 0:
        if (a,b) in d:
            d[(a,b)][0] += 1
        else:
            d[(a,b)] = [1,0]
    else:
        if (b,-a) in d:
            d[(b,-a)][1] += 1
        else:
            d[(b,-a)] = [0,1]
        


MOD = 1000000007
ans = 1

pow2 = [1]
for _ in range(200005):
    pow2.append(pow2[-1]*2%MOD)

#print(d)
for (a,b),(k,l) in d.items():
    ans *= pow2[k]+pow2[l]-1
    ans %= MOD


ans -= 1
print(ans%MOD)

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
ab = np.zeros([N, 2])
for n in range(N):
    ab[n] = input().split()
ans = 0
for n in range(N):
    ans += (ab[n:].dot(ab[n])!=0).sum() % 1000000007
print(ans)

Submission status: Wrong Answer

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    from math import gcd
    input = sys.stdin.buffer.readline

    N = int(input())
    cnt = {}
    for _ in range(N):
        a, b = map(int, input().split())
        if a == b == 0:
            continue
        if a < 0:
            a = -a
            b = -b
        g = gcd(abs(a), abs(b))
        x = (a // g, b // g)
        if x in cnt:
            cnt[x] += 1
        else:
            cnt[x] = 1

    ans = 1
    num = 0
    for x in cnt:
        if cnt[x] == 0:
            continue
        a, b = x
        if b > 0:
            y = (b, -a)
        else:
            y = (-b, a)
        if y in cnt:
            nx = cnt[x]
            ny = cnt[y]
            cnt[y] = 0
            ans = (ans * ((pow(2, nx, mod) - 1) + (pow(2, ny, mod) - 1) + 1)%mod)%mod
        else:
            num += cnt[x]
    ans = (ans * pow(2, num, mod))%mod
    ans = (ans - 1)%mod
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from math import gcd
import sys

input=sys.stdin.readline

N=int(input())
dicplus={}
dicminus={}
dicinf=0
diczero=0
dicnan=0
for i in range(N):
    a,b=map(int,input().split())
    g=gcd(a,b)
    if g==0:
        dicnan+=1
    else:
        A=a//g
        B=b//g
        if A*B>0:
            if (A,B) not in dicplus:
                dicplus[(A,B)]=0
            dicplus[(A,B)]+=1
        elif A*B<0:
            A=abs(A)
            B=abs(B)
            if (A,B) not in dicminus:
                dicminus[(A,B)]=0
            dicminus[(A,B)]+=1
        elif A!=0:
            dicinf+=1
        elif B!=0:
            diczero+=1


ans=1
mod=10**9+7
for a,b in dicplus:
    if (b,a) in dicminus:
        ans*=(pow(2,dicplus[(a,b)],mod)-1+pow(2,dicminus[(b,a)],mod)-1+1)
        ans%=mod
    else:
        ans*=pow(2,dicplus[(a,b)],mod)
        ans%=mod

for a,b in dicminus:
    if (b,a) not in dicplus:
        ans*=pow(2,dicminus[(a,b)],mod)
        ans%=mod

ans*=(pow(2,dicinf,mod)-1+pow(2,diczero,mod)-1+1)
ans%=mod

print(ans-1+dicnan)

Submission status: Wrong Answer

Solution code:
from math import gcd
import sys

input=sys.stdin.readline

N=int(input())
dicplus={}
dicminus={}
dicinf=0
diczero=0
dicnan=0
for i in range(N):
    a,b=map(int,input().split())
    g=gcd(a,b)
    if g==0:
        dicnan=1
    else:
        A=a//g
        B=b//g
        if A*B>0:
            if (A,B) not in dicplus:
                dicplus[(A,B)]=0
            dicplus[(A,B)]+=1
        elif A*B<0:
            A=abs(A)
            B=abs(B)
            if (A,B) not in dicminus:
                dicminus[(A,B)]=0
            dicminus[(A,B)]+=1
        elif A!=0:
            dicinf+=1
        elif B!=0:
            diczero+=1
    

ans=1
mod=10**9+7
for a,b in dicplus:
    if (b,a) in dicminus:
        ans*=(pow(2,dicplus[(a,b)],mod)-1+pow(2,dicminus[(b,a)],mod)-1+1)
        ans%=mod
    else:
        ans*=pow(2,dicplus[(a,b)],mod)
        ans%=mod

for a,b in dicminus:
    if (b,a) not in dicplus:
        ans*=pow(2,dicminus[(a,b)],mod)
        ans%=mod

ans*=(pow(2,dicinf,mod)-1+pow(2,diczero,mod)-1+1)
ans%=mod

print(ans-1+dicnan)

Submission status: Wrong Answer

Solution code:

N = int(input())

dic = {}
zz = 0
az = 0
bz = 0

for i in range(N):

    A,B = map(int,input().split())

    if A == B == 0:
        zz += 1
    elif A == 0:
        az += 1
    elif B == 0:
        bz += 1
    else:

        if A*B > 0:
            now = A / B
            ind = 0
        else:
            now = -1 * (B / A)
            ind = 1

        if now not in dic:
            dic[now] = [0,0]
        dic[now][ind] += 1

mod = 10**9+7
ans = pow(2,az,mod) + pow(2,bz,mod) - 1

for i in dic:

    aa,bb = dic[i]
    now = pow(2,aa,mod) + pow(2,bb,mod) - 1
    ans *= now
    ans %= mod

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

Submission status: Wrong Answer

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

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


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

Submission status: Wrong Answer

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

def gcd(x, y):
    x = abs(x)
    y = abs(y)

    if x < y:
        x, y = y, x

    while y:
        x, y = y, x%y
        
    return x

N = int(input())
seen = dict()
zeroes = 0
for _ in range(N):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zeroes += 1
        continue
    
    if a < 0:
        a, b = -a,-b
    if b <= 0:
        a, b = -b, a
        flip = 1
    else:
        flip = 0
    g = gcd(a,b)
    a//=g
    b//=g
    if (a,b) not in seen:
        seen[(a,b)] = [0,0]
    
    seen[(a,b)][flip] += 1

MOD = 10 ** 9 + 7
    
out = 1
for v in seen:
    a, b = seen[v]
    out *= (pow(2,a,MOD) + pow(2,b,MOD) - 1)
    out %= MOD
out -= 1
out += zeroes
out %= MOD
print(out)

Submission status: Wrong Answer

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

def gcd(x, y):
    x = abs(x)
    y = abs(y)

    if x < y:
        x, y = y, x

    while y:
        x, y = y, x%y
        
    return x

N = int(input())
seen = dict()
zeroes = 0
for _ in range(N):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zeroes += 1
        continue
    
    if a < 0:
        a, b = -a,-b
    if b <= 0:
        a, b = -b, a
        flip = 1
    else:
        flip = 0
    g = gcd(a,b)
    a//=g
    b//=g
    if (a,b) not in seen:
        seen[(a,b)] = [0,0]
    
    seen[(a,b)][flip] += 1

MOD = 10 ** 9 + 7
    
out = 1
for v in seen:
    a, b = seen[v]
    out *= (pow(2,a,MOD) + pow(2,b,MOD) - 1)
    out %= MOD
out -= 1
out %= MOD
print(out + zeroes)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import math
mod = 10**9 + 7
n = int(input())
a = [0] *n
b = [0] * n
que = deque()
for i in range(n):
  A,B = map(int, input().split())
  a[i] = A
  b[i] = B

t = set()
for i in range(n):
  x,y = a[i],b[i]
  for j in range(i,n):
    if x*a[j] + y*b[j] == 0:
      que.append([i,j])
      t.add(i)
      t.add(j)

ans = 1
for k in range(1,n):
  ans += (math.factorial(n) / (math.factorial(k) * math.factorial(n-k))) % mod

while que:
  na = que.pop()
  m = len(na)
  for k in range(m,n+1):
    ans -= (math.factorial(n-m) / (math.factorial(k-m) *  math.factorial(n-k))) % mod

for d in range(3,len(t)+1):
  for k in range(d,n+1):
    ans += (math.factorial(n-d) / (math.factorial(k-d) *  math.factorial(n-k))) % mod

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7
P = 7 ** 21 + 52


def F(a, b):
    return (a * pow(b, P-2, P)) % P


def main():
    from collections import Counter
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    T = [[int(i) for i in input().split()] for j in range(N)]
    A = []
    cnt_zero = [0, 0]  # 片方が0のとき
    p = 0  # 両方0
    cA = Counter()
    for a, b in T:
        if a == 0 and b == 0:
            p += 1
        elif a == 0:
            cnt_zero[0] += 1
        elif b == 0:
            cnt_zero[1] += 1
        else:
            A.append((F(a, b), -F(b, a) % P))
            cA[F(a, b)] += 1

    used = set()
    ans = 1
    ans *= pow(2, cnt_zero[0], MOD) - 1 + pow(2, cnt_zero[1], MOD) - 1 + 1
    for a, b in A:
        if a in used or b in used:
            continue
        ans *= pow(2, cA[a], MOD) - 1 + pow(2, cA[b], MOD) - 1 + 1
        ans %= MOD
        used.add(a)
        used.add(b)
    print((ans + p - 1) % MOD)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import Fraction as F
MOD = 10**9 + 7


def main(N, T):
    A = []
    cnt_zero = [0, 0]  # 片方が0のとき
    p = 0  # 両方0
    cA = {}
    for a, b in T:
        if a == 0 and b == 0:
            p += 1
        elif a == 0:
            cnt_zero[0] += 1
        elif b == 0:
            cnt_zero[1] += 1
        else:
            A.append((F(a, b), F(b, a)))
            if F(a, b) not in cA.keys():
                cA[F(a, b)] = 0
            if -F(b, a) not in cA.keys():
                cA[-F(b, a)] = 0
            cA[F(a, b)] += 1

    used = set()
    ans = 1
    ans *= pow(2, cnt_zero[0], MOD) - 1 + pow(2, cnt_zero[1], MOD) - 1 + 1
    for a, b in A:
        if a in used or -b in used:
            continue
        ans *= pow(2, cA[a], MOD) - 1 + pow(2, cA[-b], MOD) - 1 + 1
        ans %= MOD
        used.add(a)
        used.add(-b)
    print((ans + p - 1) % MOD)


if __name__ == '__main__':

    N = int(input())
    T = [[int(i) for i in input().split()] for j in range(N)]
    main(N, T)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7


def main():
    from fractions import Fraction as F
    N = int(input())
    A = []
    cnt_zero = [0, 0]  # 片方が0のとき
    p = 0  # 両方0
    cA = {}
    for _ in range(N):
        a, b = (int(i) for i in input().split())
        if a == 0 and b == 0:
            p += 1
        elif a == 0:
            cnt_zero[0] += 1
        elif b == 0:
            cnt_zero[1] += 1
        else:
            A.append((F(a, b), F(b, a)))
            if F(a, b) not in cA.keys():
                cA[F(a, b)] = 0
            if -F(b, a) not in cA.keys():
                cA[-F(b, a)] = 0
            cA[F(a, b)] += 1

    used = set()
    ans = 1
    ans *= pow(2, cnt_zero[0], MOD) - 1 + pow(2, cnt_zero[1], MOD) - 1 + 1
    for a, b in A:
        if a in used or -b in used:
            continue
        ans *= pow(2, cA[a], MOD) - 1 + pow(2, cA[-b], MOD) - 1 + 1
        ans %= MOD
        used.add(a)
        used.add(-b)
    print((ans + p - 1) % MOD)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7


def main():
    from fractions import Fraction as F
    from collections import Counter

    N = int(input())
    A = []
    cnt_zero = [0, 0]  # 片方が0のとき
    p = 0  # 両方0
    cA = Counter()
    for _ in range(N):
        a, b = (int(i) for i in input().split())
        if a == 0 and b == 0:
            p += 1
        elif a == 0:
            cnt_zero[0] += 1
        elif b == 0:
            cnt_zero[1] += 1
        else:
            A.append((F(a, b), F(b, a)))
            cA[F(a, b)] += 1

    used = set()
    ans = 1
    ans *= pow(2, cnt_zero[0], MOD) - 1 + pow(2, cnt_zero[1], MOD) - 1 + 1
    for a, b in A:
        if a in used or -b in used:
            continue
        ans *= pow(2, cA[a], MOD) - 1 + pow(2, cA[-b], MOD) - 1 + 1
        ans %= MOD
        used.add(a)
        used.add(-b)
    print((ans + p - 1) % MOD)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
n = int(input())
s, h = [], []
p = 0
for _ in range(n):
	s.append(list(map(int, input().split())))

for i in range(len(s)):
	for j in range(i+1, n):
		if s[i][0]*s[j][0] + s[i][1]*s[j][1] == 0: h.append((i, j))

def comb(li):
	count = 0
	if len(li[0]) == 1: return len(li)
	for l in li:
		com = set(list(combinations(l, 2)))
		if len(com & set(h)) == 0:
			count += 1
	return count

for i in range(1, n+1):
	l = list(combinations(range(0, n), i))
	p += comb(l)
print(p % 1000000007)