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 bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 1000000007

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]
def init_dp1(init, N): return [init for _ in range(N)]
def init_dp2(init, N, M): return [[init for _ in range(M)] for _ in range(N)]


def f(v, k, L, K, A):
    p = v[0]
    t = -1 / k
    if t in K:
        return t

    i = bisect.bisect_right(L, t)
    if i != len(L):
        q = K[L[i]][0]
        if A[p][0] * A[q][0] + A[p][1] * A[q][1] == 0:
            return L[i]

    if i + 1 < len(L):
        q = K[L[i + 1]][0]
        if A[p][0] * A[q][0] + A[p][1] * A[q][1] == 0:
            return L[i + 1]
    
    if i > 0:
        q = K[L[i - 1]][0]
        if A[p][0] * A[q][0] + A[p][1] * A[q][1] == 0:
            return L[i - 1]

    return t


def main():
    N = int(input())
    A = read_lists(N)    

    K = {}
    zero = 0
    for i, a in enumerate(A):
        if a == [0, 0]:
            zero += 1
            continue

        if a[0] == 0:
            r = 10 ** 20
        else:
            r = a[1] / a[0]
        K.setdefault(r, []).append(i)

    L = sorted(list(K.keys()))    

    S = set()
    res = 1
    for k, v in K.items():
        if k in S:
            continue
        S.add(k)

        if k == 0:
            t = 10 ** 20
        elif k == 10 ** 20:
            t = 0
        else:
            t = f(v, k, L, K, A)

        if t in K:
            S.add(t)
            v2 = K[t]
            res *= (pow(2, len(v), mod) + pow(2, len(v2), mod) - 1) % mod
            res %= mod
        else:
            res *= 2
            res %= mod

    print((res + zero - 1) % mod)
 

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

mod = 1000000007
eps = 0.0000000000001

n = int(input())

ab = []
ang = []
half = math.pi/2.0

for i in range(n):
    a,b = map(int,input().split())
    ab.append((a,b))
    if a == 0:
        ang.append(half)
    else:
        ang.append(math.atan(b/a))
ang.sort()

res = 1
rest = n

i = 0
while True:
    if i >= n:
        break
    val = ang[i]
    if val > 2*eps:
        break
    cnt = bisect.bisect_right(ang,val+eps) - i
    cnt2 = bisect.bisect_right(ang,val+half+eps) - bisect.bisect_left(ang,val+half-eps)
    if cnt2 > 0:
        rest = rest - cnt - cnt2
        res = res*(pow(2,cnt,mod) + pow(2,cnt2,mod) - 1)%mod
    i += cnt
rest = max(rest,0)
res = res*pow(2,rest,mod)%mod - 1
print(res%mod)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N = int(input())
mod = 1000000007

# 両方の符号が同じやつ同士は必ず相性が悪くならない
# 符号が異なる数字の組み合わせと両方の符号が同じ奴が相性が悪くなる 
k = []
d = defaultdict(int)
cnt = 0
for i in range(N):
    a, b = map(int, input().split())
    if a * b > 0:
        cnt += 1
        key = str(a*10**20+b)
        d[key] += 1
    else:
        k.append([min(a, b), max(a, b)])

# からの状態を引く
ans = pow(2, cnt, mod) - 1

for a, b in k:
    a = -a
    key = str(a*10**20+b)
    if d[key] == 0:
        ans *= 2
    else:
        ans += pow(2, N-d[key]-1, mod)
    ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[]
b=[]
for i in range(n):
    ai,bi=map(int,input().split())
    a.append(ai)
    b.append(bi)

c=[]
for i in range(n):
    for j in range(n):
        if a[i]*a[j]+b[i]*b[j]==0:
            ij=[i,j]
            c.append(ij)

s=0
for i in range(2**n):
    d=[]
    for j in range(n):
        if ((i>>j) & 1):
            d.append(j)
    t=0
    for j in range(len(c)):
        e=0
        if c[j][0] in d:
            e+=1
        if c[j][1] in d:
            e+=1
        if e!=2:
            t=1
    if t==1:
        s+=1

print((s-1)%1000000007)

Submission status: Wrong Answer

Solution code:
import sys

def main():
    input = sys.stdin.readline
    mod = pow(10,9)+7
    
    n = int(input())
    key1 = dict()
    key2 = dict()
    
    a_0 = 0
    b_0 = 0
    ab_0 = 0
    
    for i in range(n):
        a, b = map(int, input().split())
        if a == 0 and b == 0:
            ab_0 += 1
            continue
        if a == 0:
            a_0 += 1
            continue
        if b == 0:
            b_0 += 1
            continue
        k1, k2 = abs(a), abs(b)
        if k2 > k1:
            k1, k2 = k2, k1
        while k2%k1:
            k2, k1 = k1, k2%k1
        a //= k1
        b //= k1
        if a*b > 0:
            if a/b in key1:
                key1[a/b] += 1
            else:
                key1[a/b] = 1
        else:
            if abs(b/a) in key2:
                key2[abs(b/a)] += 1
            else:
                key2[abs(b/a)] = 1
    ans = 0
    ans += (ab_0*(n-ab_0)+(ab_0-1)*ab_0//2)%mod
    ans += (a_0*b_0)%mod
    ans %= mod
    
    left = n-(ab_0+a_0+b_0)
    judge = 0
    for k1, v1 in key1.items():
        if k1 in key2:
            v2 = key2[k1]
            left += -v1-v2
            ans += (((v1*v2*pow(2, left, mod))%mod)*(judge+1))%mod
            ans %= mod
            judge += (judge*(v1+v2))%mod
            judge += v1+v2
            judge %= mod
            
    
    ans = ((pow(2, n, mod)-1)+2*mod-ans)%mod
          
    
    print(ans)
    


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
import sys
sys.setrecursionlimit(10**9)
from collections import deque,defaultdict
import heapq
from itertools import combinations
import bisect


mod=10**9+7

n=int(input())

dp=defaultdict(int)
dm=defaultdict(int)
z=0
ans=0
cp=[]
cm=[]
az=0
bz=0
cz=0
mod2=10**20+9
for i in range(n):
    a,b=map(int,input().split())
    if a*b>0:
        p=(abs(a)*pow(abs(b),mod2-2,mod2))%mod2
        pp=(abs(b)*pow(abs(a),mod2-2,mod2))%mod2
        if dp[p]==0:
            cp.append([p,pp])
        dp[p]+=1
    elif a*b<0:
        p=(abs(a)*pow(abs(b),mod2-2,mod2))%mod2
        dm[p]+=1
    elif a==b==0:
        cz+=1
    elif a==0:
        az+=1
    elif b==0:
        bz+=1

kk=pow(2,az,mod)+pow(2,bz,mod)-1
if kk>0:
    ans=kk
else:
    ans=1
z=n-(az+bz+cz)
for a,b in cp:
    ans*=pow(2,dp[a],mod)+pow(2,dm[b],mod)-1
    ans%=mod
    z-=(dp[a]+dm[b])
# print(z)
ans*=pow(2,z,mod)

print((ans-1)%mod)

Submission status: Wrong Answer

Solution code:
n = int(input())
MOD = 1000000007

ans = 1
x_sardines = []
ver_sardines = []
hor_sardines  = []
zero_sardines  = []

for _ in range(n):
  ai, bi = map(int, input().split())
  if ai == 0 and bi != 0:
    ver_sardines.append((ai, bi))
  elif ai != 0 and bi == 0:
    hor_sardines.append((ai, bi))
  elif ai == 0 and bi == 0:
    zero_sardines.append((ai, bi))
  elif bi / ai > 0:
    x_sardines.append((ai, bi, 1))
  elif bi / ai < 0:
    x_sardines.append((- 1 * bi, ai, -1))

x_sardines.sort(key = lambda x: x[1] / x[0])

if len(x_sardines) > 0:
  pai, pbi, ps = x_sardines[0]
  p = 1 if ps == 1 else 0
  n = 1 if ps == -1 else 0
  for i, (ai, bi, s) in enumerate(x_sardines[1:]):
    if pai * bi - pbi * ai != 0:
      ans *= pow(2, p, MOD) + pow(2, n, MOD) - 1
      ans %= MOD
      p = 0
      n = 0
      
    if s == 1:
      p += 1
    elif s == -1:
      n += 1
    pai, pbi, ps = ai, bi, s

  ans *= pow(2, p, MOD) + pow(2, n, MOD) - 1
  ans %= MOD
  
v = len(ver_sardines)
h =  len(hor_sardines)
ans *= pow(2, v, MOD) + pow(2, h, MOD) - 1
ans %= MOD

z = len(zero_sardines)
ans += pow(2, z, MOD) - 1 
ans -= 1
ans %= MOD

print(ans)

Submission status: Wrong Answer

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

from collections import defaultdict, deque
from sys import exit
import math
import copy
from bisect import bisect_left, bisect_right
from heapq import *
import sys
# sys.setrecursionlimit(1000000)
INF = 10 ** 17
MOD = 1000000007

from fractions import *
def inverse(f):
    # return Fraction(f.denominator,f.numerator)
    return 1/f


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

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

    return ret

def solve():
    n = getN()
    iwashis = []
    zz = 0
    fr = defaultdict(int)
    for i in range(n):
        iw = getList()
        if iw[0] == 0 and iw[1] == 0:
            zz += 1
            continue
        if iw[0] != 0:
            # fr[Fraction(iw[1], iw[0])] += 1
            fr[iw[1]/iw[0]] += 1
        else:
            fr["INF"] += 1

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


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

"""
12
3 2
3 2
0 1
2 -1
-3 -9
-8 12
7 0
8 1
8 2
8 4
0 0
0 0
"""

Submission status: Wrong Answer

Solution code:
def modpow(a, n, p):
  if n <= 0:
    return 1
  if n == 1:
    return a % p 
  elif n % 2 == 1:
    return a * modpow(a, n-1, p) % p
  else:
    return modpow(a, n//2, p) **2 % p
MOD = 1000000007
n = int(input())
dct1 = {}
dct2 = {}
l = []
for i in range(n):
  a, b = map(int, input().split())
  l.append((a, b))
  if a == 0:
    dct1["a0"] = dct1.get("a0", 0) + 1
  elif b == 0:
    dct1["b0"] = dct1.get("b0", 0) + 1
  else:
    dct1[a/b] = dct1.get(a/b, 0) + 1
    dct2[-b/a] = dct2.get(-b/a, 0) + 1

count = 0
for i in range(n):
  a, b = l[i]
  l.append((a, b))
  if a == 0:
    count += modpow(2, n-1-i-dct1.get("b0",0), MOD)
  elif b == 0:
    count += modpow(2, n-1-i-dct1.get("a0",0), MOD)
  else:
    count += modpow(2, n-1-i-dct2.get(a/b, 0), MOD)
print(count % MOD)

Submission status: Wrong Answer

Solution code:
from math import gcd
from collections import Counter
N, *A = map(int, open(0).read().split())
*A, = zip(*[iter(A)]*2)

mod = 10**9 + 7


def modpow(a, n, mod):
    ret = 1
    while n:
        if n & 1:
            ret = ret * a % mod
        a = a * a % mod
        n >>= 1
    return ret

col = []
row = []
zero = False
for a, b in A:
    if a == b == 0:
        zero = True
        continue
    if a == 0:
        col.append((1,0))
        continue
    elif b == 0:
        row.append((1,0))
        continue

    c = a/b
    if c > 0:
        col.append((c))
    else:
        row.append((-1/c))

C = Counter(col)
D = Counter(row)
S = set(col) | set(row)

ans = 1
for s in S:
    if s in C:
        if s in D:
            mul = modpow(2, C[s], mod) + modpow(2, D[s], mod) - 1
            mul %= mod
        else:
            mul = modpow(2, C[s], mod)
    elif s in D:
        mul = modpow(2, D[s], mod)

    ans *= mul
    ans %= mod

ans -= 1
if zero:
    ans += 1
ans %= mod

print(ans)

Submission status: Wrong Answer

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

def powmod(a,p):
  if p==0:
    return 1
  else:
    pow2=powmod(a,p//2)
    if p%2==0:
      return (pow2**2)%MOD
    else:
      return (a*pow2**2)%MOD

num_dic=defaultdict(int)
zero_num=0
inf_num=0

dp=[-1]*(N+1)
dp[0]=1
for i in range(1,N+1):
  a,b=map(int,input().split())
  if a==0 and b==0:
    dp[i]=dp[i-1]
  elif a==0:
    dp[i]=dp[i-1]+powmod(2,i-1-inf_num)
    dp[i]%=MOD
    zero_num+=1
  elif b==0:
    dp[i]=dp[i-1]+powmod(2,i-1-zero_num)
    dp[i]%=MOD
    inf_num+=1
  else:
    dp[i]=dp[i-1]+powmod(2,i-1-num_dic[-b/a])
    dp[i]%=MOD
    num_dic[a/b]+=1

#print(dp)
print(dp[N]-1)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def serch(M,now,after):
    cnt = 0
    for j in range(M):
        temp = np.dot(now,after[j])
        if temp != 0:
            cnt += 1
            # print(now)
            # print(after[j])
    # print(M,cnt)
    return cnt


def loop(N,AB,mod):
    res = 0
    for i in range(N):
        res += serch(N-i-1,AB[i,:],AB[i+1:,:])
        # res %= mod
    return res


def main():
    N = int(input())
    AB = np.array([list(map(int,input().split())) for i in range(N)])

    mod = 1000000007

    res = 2 ** N - loop(N,AB,mod) - 1
    res %= mod

    print(res)



main()

Submission status: Wrong Answer

Solution code:
from _collections import defaultdict
n=int(input())
mod=10**9+7
X=[]
Y=[]
count=0
for i in range(n):
    a,b=map(int,input().split())
    if a==0 or b==0:
        count+=1
    else:
        X.append(-a/b)
        Y.append(b/a)

P=defaultdict(float)
Q=defaultdict(float)
for x in X:
    P[x]+=1
for y in Y:
    Q[y]+=1
print(P)
print(Q)
p=P.keys()
q=Q.keys()
r=p&q
B=[]
for i in r:
    if abs(i)>=1:
        B.append(i)
        
tot=n
ans=1
for i in B:
    ans*=(P[i]+Q[i]+1)
    ans%=mod
    tot-(P[i]+Q[i])
ans*=pow(2,tot,mod)
ans%=mod
ans*=(count+1)
ans%=mod
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin, setrecursionlimit


def main():
    mod = 10 ** 9 + 7
    input = stdin.buffer.readline
    n = int(input())
    p = []
    m = []

    for _ in range(n):
        a, b = map(int, input().split())
        if a != 0 and b != 0:
            f = b / a
            if b / a < 0:
                m.append(-a / b)
            elif f > 0:
                p.append(b / a)
        else:
            m.append(0)

    g_p = {}
    for k in p:
        if k in g_p:
            g_p[k] += 1
        else:
            g_p[k] = 1
    g_m = {}
    for k in m:
        if k in g_m:
            g_m[k] += 1
        else:
            g_m[k] = 1

    ans = 1

    for k in g_p:
        if k in g_m:
            ans *= (2 ** g_p[k] + 2 ** g_m[k] - 1)
        else:
            ans *= 2 ** g_p[k]
        ans %= mod
    for k in g_m:
        if k == 0:
            ans *= (g_m[k] + 1)
        elif not (k in g_p):
            ans *= 2 ** g_m[k]
            ans %= mod
    print((ans - 1) % mod)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict as dd
from math import gcd
input = sys.stdin.readline
N = int(input())
mod = 10 ** 9 + 7
d = dd(int)
a = [tuple(map(int, input().split())) for _ in range(N)]
for x, y in a:
  g = gcd(abs(x), abs(y))
  if g == 0: g = 1
  d[(x // g, y // g)] += 1
res = 1
u = 0
itr = list(d.keys())
#print(itr)
for x, y in itr:
  t = d[(y, -x)] + d[(-y, x)]
  if t == 0: u += d[(x, y)]
for x, y in itr:
  t = 0
  if (x, y) == (0, 0):
    res *= d[(x, y)] + 1
    continue
  elif (y, -x) == (-y, x):
    t = d[(y, -x)]
  else:
    t = d[(y, -x)] + d[(-y, x)]

  if t:
    v = 0
    v += pow(2, d[(x, y)], mod) - 1
    v %= mod
    v += pow(2, t, mod) - 1
    v %= mod
    v += 1
    v %= mod
    res *= v
    res %= mod
    #print(res, v)
  d[(x, y)] = 0
#print(itr, u, res)
print(res * pow(2, u, mod) - 1 % mod)

Submission status: Wrong Answer

Solution code:
import math
MOD =1000000007


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

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2
        # print(K,x)
        x%=MOD
    return K * x


n = int(input())

a_b_d = {}

a_zero_cnt = 0
b_zero_cnt = 0
ab_zero_cnt = 0

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


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


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

zero_m = max(pow_k(2,a_zero_cnt) + pow_k(2,b_zero_cnt) + ab_zero_cnt-1, 1)
ans *= zero_m
ans -= 1
print(ans%MOD)

Submission status: Wrong Answer

Solution code:
from collections import Counter
mod = 1000000007
N = int(input())
AB = Counter()
x = set()
for _ in range(N):
    a, b = map(int, input().split())
    AB[a*b] += 1
    if AB[-a*b] > 0:
        x.add(abs(a*b))

cnt = 0

res = 1
for i in x:
    ares = res
    
    a = 1
    for _ in range(AB[i]):
        a *= 2
        a %= mod
    a -= 1
    if a < 0:
        a += mod
    res += ares*a
    cnt += AB[i]


    a = 1
    for _ in range(AB[-i]):
        a *= 2
        a %= mod
    a -= 1
    if a < 0:
        a += mod
    res += ares*a
    cnt += AB[-i]

a = 1
for _ in range(N-cnt):
    a *= 2
    a %= mod
a -= 1
if a < 0:
    a += mod
res += res*a

print(res-1)

Submission status: Wrong Answer

Solution code:
import math
import collections

n = int(input())
iwashi = [None for _ in range(n)]
for i in range(n):
    a, b = map(int, input().split())
    iwashi[i] = (math.degrees(math.atan2(a, b)) + 180) % 180
# print(iwashi)
iwashi = collections.Counter(iwashi)
k_list = list(iwashi.keys())
v = list(iwashi.values())
# k_list.sort(key=lambda x: -x)

mod = 1000000007
ans = 1
counter = 0
for k in k_list:
    a = iwashi[k]
    b = iwashi[k+90] + iwashi[k-90]
    if a*b != 0:
        ans *= (pow(2, a, mod) + pow(2, b, mod) -1)
        if a+b == b:
            ans += 1
    else:
        ans *= pow(2, a, mod)
    iwashi[k] = 0
    iwashi[k+90] = 0
    iwashi[k-90] = 0
    # print(a, b, ans)
    ans %= mod
if counter == 0:
    print(ans-2)
else:
    print(ans-1)

Submission status: Wrong Answer

Solution code:
mod = 1000000007
import collections
n = int(input())
dat1 = []
dat2 = []
for i in range(n):
    a,b = map(int, input().split())
    dat1.append(a)
    dat2.append(b)
ngfish = []
for i in range(n):
    res = 0
    for j in range(i+1, n):
        if dat1[i] * dat1[j] + dat2[i] * dat2[j] == 0:
            res += 1
    ngfish.append(res)

#print(ngfish)

res = 0
for i in range(len(ngfish)):
    res += pow(2, n - i - 1 - ngfish[i], mod)
    res %= mod
print(res)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import math

MOD = 1000000007  # type: int


def pow2(x):
    res = 1
    a = 2
    while x > 0:
        if x & 1:
            res = (res * a) % MOD
        a = a * a % MOD
        x >>= 1
    return res

def solve(N: int, A: "List[int]", B: "List[int]"):
    m = {}

    for i in range(N):
        if A[i] == 0 and B[i] == 0:
            if "0" in m:
                m["0"][0] += 1
            else:
                m["0"] = [1, 0, 0]
            continue
        if A[i] == 0:
            if "0" in m:
                m["0"][1] += 1
            else:
                m["0"] = [0, 1, 0]
            continue
        if B[i] == 0:
            if "0" in m:
                m["0"][2] += 1
            else:
                m["0"] = [0, 0,1]
            continue


        gcd = math.gcd(A[i],B[i])

        a = A[i] // gcd
        b = B[i] // gcd
        if (a < 0 and b < 0 ) or (a > 0 and b > 0):
            key = str(abs(a)) + "/" + str(abs(b))
            if key in m:
                m[key][0] += 1
            else:
                m[key] = [1, 0]
        else:
            key =str(abs(b)) + "/" + str(abs(a))
            if key in m:
                m[key][1] += 1
            else:
                m[key] = [0, 1]

    ans = 1
    for k, v in m.items():
        if k == "0":
            ans = (ans * (pow2(v[1]) + pow2(v[1])  + v[0] - 1)) % MOD
        else:
            ans = (ans * (pow2(v[0]) + pow2(v[1]) - 1)) % MOD
    print(ans-1)
            
        

    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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:
N=int(input())
src = []
srca = []
srcb = []
s=[0]*N
ind=0
for n in range(N):
  a=list(map(int,input().split()))
  src.append(a)
  x=a[0]
  y=a[1]
  for j in range(len(src)-1):
    l=src[j]
    if (l[0]*x+l[1]*y)==0:
      ind+=1
ans=2**N-(2**(N-ind-1))-1
print(ans%(7*10**9))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15
dy = (-1,0,1,0)
dx = (0,1,0,-1)
from math import gcd

def main():
    N = int(input())
    minus_iwashi = {}
    iwashi = {}
    a0 = 0
    b0 = 0
    a0b0 = 0
    
    for _ in range(N):
        a,b = map(int,input().split())
        if a < 0 and b > 0:
            a = -a
            b = -b
        elif a < 0 and b < 0:
            a = -a
            b = -b
        if a == 0 and b == 0:
            a0b0 += 1
            continue
        if a == 0 and b != 0:
            a0 += 1
            continue
        if b == 0 and a != 0:
            b0 += 1
            continue
        #print(a,b)
        if b < 0:
            a,b = -b,a
            #print('mini{}{}'.format(a,b))
            x = gcd(a,b)
            a //= x
            b //= x
            if (a,b) in minus_iwashi:
                minus_iwashi[(a,b)] += 1
            else:
                minus_iwashi[(a,b)] = 1
        elif b > 0:
            x = gcd(a,b)
            a //= x
            b //= x
            if (a,b) in iwashi:
                iwashi[(a,b)] += 1
            else:
                iwashi[(a,b)] = 1
    
    power = [1]
    for _ in range(N):
        power.append(power[-1]*2%MOD)
    '''
    print(power)
    print(iwashi)
    print(minus_iwashi)
    print(a0,b0)
    '''
    
    if a0 > 0 and b0 > 0:
        ans = (power[a0] + power[b0] - 1)%MOD
    elif a0 > 0:
        ans = power[a0]
    elif b0 > 0:
        ans = power[b0]
    else:
        ans = 1

    for k,v in iwashi.items():
        if k in minus_iwashi:
            ans *= (power[v] + power[minus_iwashi[k]] - 1)%MOD
            ans %= MOD
        else:
            ans *= power[v]
            ans %= MOD
    
    for k,v in minus_iwashi.items():
        if k in iwashi:
            continue
        else:
            ans *= power[v]
            ans %= MOD
    if a0b0 > 0:
        ans += power[a0b0] - 1
    print((ans - 1)%MOD)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin, setrecursionlimit
input = stdin.buffer.readline
setrecursionlimit(10 ** 7)

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi

MOD = 10 ** 9 + 7
INF = 10 ** 18
SIZE = 3 * 10 ** 5

g1, g2, inv = [1, 1], [1, 1], [0, 1]
for i in range(2, SIZE + 1):
    g1.append((g1[-1] * i) % MOD)
    inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
    g2.append((g2[-1] * inv[-1]) % MOD)
    
def comb(n, r):
    if r < 0 or r > n:
        return 0
    r = min(r, n - r)
    return g1[n] * g2[r] * g2[n - r] % MOD

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

cnt = defaultdict(int)
zero = 0
for a, b in AB:
    if a != 0 and b != 0:
        cnt[b / a] += 1
    else:
        zero += 1
#print(cnt)


answer = 1
rest = N

if zero >= 2:
    answer *= 1 + zero
    answer %= MOD
rest -= zero

cnt2 = defaultdict(int)
for a, b in AB:
    if a != 0 and b != 0 and b / a > 0:
        if cnt[b / a] and cnt[- a / b] and cnt2[b / a] == 0:
            cnt2[b / a] = 1
            rest -= cnt[b / a] + cnt[- a / b]
            answer *= pow(2, cnt[b / a] + cnt[- a / b], MOD) - (pow(2, cnt[- a / b], MOD) - 1) * (pow(2, cnt[b / a], MOD) - 1) 
            answer %= MOD
answer *= pow(2, rest, MOD)
answer -= 1
answer %= MOD

print(answer)

Submission status: Wrong Answer

Solution code:
from fractions import Fraction
import sys
input = sys.stdin.readline
def powmod(x, n,mod):
  if n == 0:
   return 1
  K = 1
  while n > 1:
   if n % 2 != 0:
    K = K * x%mod
    x = x ** 2%mod
    n = (n - 1) // 2
   else:
    x = x ** 2%mod
    n = n // 2%mod

  return K * x # 指数を割り続け n が 1 に至ったら終了
N=int(input())
mod=10**9+7
dic={}
dica={}
c=0
d=0
e=0
for i in range(N):
 A,B = map(int,input().split())
 if A==0 and B==0:
  e+=1
 elif A==0:
  c+=1
 elif B==0:
  d+=1
 else:
   x=Fraction(A,B)
   if x>0:
    if x in dic:
     dic[x]+=1
    else:
     dic[x]=1
   else:
    if x in dic:
     dica[x]+=1
    else:
     dica[x]=1
ans=1
for k in dic:
 if -1/k in dica:
   ans*=(powmod(2,dic[k],mod)+powmod(2,dica.pop(-1/k),mod) -1)
 else:
   ans*=powmod(2,dic[k],mod)
 ans%=mod
for k in dica:
 ans*=powmod(2,dica[k],mod)
 ans%=mod
ans*=(powmod(2,c,mod)+powmod(2,d,mod)-1)
ans%=mod
print(ans-1+e)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
import sys
sys.setrecursionlimit(10**9)
from collections import deque,defaultdict
import heapq
from itertools import combinations
import bisect


mod=10**9+7

n=int(input())

dp=defaultdict(int)
dm=defaultdict(int)
z=0
ans=0
cp=[]
cm=[]
az=0
bz=0
cz=0
mod2=10**20+7
for i in range(n):
    a,b=map(int,input().split())
    if a*b>0:
        p=(abs(a)*pow(abs(b),mod2-2,mod2))%mod2
        pp=(abs(b)*pow(abs(a),mod2-2,mod2))%mod2
        if dp[p]==0:
            cp.append([p,pp])
        dp[p]+=1
    elif a*b<0:
        p=(abs(a)*pow(abs(b),mod2-2,mod2))%mod2
        dm[p]+=1
    elif a==b==0:
        cz+=1
    elif a==0:
        az+=1
    elif b==0:
        bz+=1

kk=pow(2,az,mod)+pow(2,bz,mod)-1
if kk>0:
    ans=kk
else:
    ans=1
z=n-(az+bz+cz)
for a,b in cp:
    ans*=pow(2,dp[a],mod)+pow(2,dm[b],mod)-1
    ans%=mod
    z-=(dp[a]+dm[b])
# print(z)
ans*=pow(2,z,mod)

print((ans-1)%mod)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def rev(a,b):
    if b<0:
        return (-b,a)
    else:
        return (b,-a)

import math
n = inn()
ab = []
h = defaultdict(int)
badpairs = {}
ab0 = a0 = b0 = 0
for i in range(n):
    a,b = inm()
    if a==b==0:
        ab0 += 1
    elif a==0:
        a0 += 1
    elif b==0:
        b0 += 1
    else:
        g = math.gcd(a,b)
        a //= g
        b //= g
        if a<0:
            a = -a
            b = -b
        h[(a,b)] += 1
        ra,rb = rev(a,b)
        if (ra,rb) in h:
            badpairs[(a,b)] = badpairs[(ra,rb)] = 1
#ddprint(h)
#ddprint(f"a0 {a0} b0 {b0} ab0 {ab0}")
grps = []
g0 = 0
if a0>0 and b0>0:
    grps.append(pow(2,a0,R)+pow(2,b0,R)-1)
done = {}
for a,b in h:
    if (a,b) in badpairs:
        if (a,b) not in done:
            ra,rb = rev(a,b)
            grps.append(pow(2,h[(a,b)],R)+pow(2,h[(ra,rb)],R)-1)
            done[(a,b)] = done[(ra,rb)] = 1
    else:
        g0 = (g0 + h[(a,b)]) % R
prod = pow(2,g0,R)
for x in grps:
    prod = (prod * x)%R
print((ab0+max(0,prod-1))%R)

Submission status: Wrong Answer

Solution code:
import math
M = 10**9+7
def getRev(a,b):
    if -b>0:
        return (-b,a)
    else:
        return (b,-a)

def main():
    n = int(input())
    
    d = {}
    
    for _ in range(n):
        a,b = tuple(map(int,input().split()))
        if a<0:
            a,b = -a,-b
        e1,e2 = 0,0
        if a!=0 and b!=0:
            g = math.gcd(abs(a),abs(b))
            e1,e2 = a//g,b//g
        else:
            g = max(a,b)
            if g!=0:
                e1,e2 = a//g,b//g
        k = e1,e2
        d.setdefault(k,0)
        d[k] += 1

    ans = 1
    for k,v in d.items():
        if k == (0,0):
            pass
        else:
            k_r = getRev(*k)
            if k_r in d:
                if d[k_r]!=-1 and d[k]!=-1:
                    v2 = d[k_r]
                    ans *= (pow(2,v,M)+pow(2,v2,M)-1)
                    ans %= M
                    d[k] = -1
                    d[k_r] = -1
            else:
                ans*=pow(2,v,M)
                ans %= M

    print(ans-1)



        

if __name__ == "__main__":
    main()