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: Runtime Error

Solution code:
import math

def make_key(a, b):
    g = math.gcd(a, b)
    a //= g
    b //= g
    # make sure a is always positive
    if a < 0:
        a *= -1
        b *= -1
    return (a, b)


def main():
    MOD = 1000000007

    N = int(input())
    keys = [make_key(*[int(x) for x in input().split()]) for _ in range(N)]

    import collections
    count = collections.Counter(keys)
    seen = set()
    ans = pow(2, N, MOD) - 1
    ans %= MOD

    # find pairs
    pairs = []
    num = N
    for key in count.keys():
        if key in seen:
            continue
        okey = make_key(key[1], -key[0])
        if okey in count:
            seen.add(key)
            seen.add(okey)
            n1 = count[key]
            n2 = count[okey]

            num -= (n1+n2)
            pairs.append((n1, n2))

    ans = pow(2, num, MOD)
    for n1, n2 in pairs:
        num = ans
        ans += (pow(2, n1, MOD)-1) * num
        ans %= MOD
        ans += (pow(2, n2, MOD)-1) * num
        ans %= MOD
        # ans += num
        # ans %= MOD
    ans -= 1

    # print(count)
    print(ans)
 
 
if __name__ == '__main__':
    import sys
    sys.setrecursionlimit(10000)
    main()

Submission status: Runtime Error

Solution code:
# RE
import math
n = int(input())
a = [0] * n;  b = [0] * n;
for i in range(n):
    a[i], b[i] = [int(x) for x in input().split()]
p = 10 ** 9 + 7

# d = [0] * n
dict = {}
for i in range(n):
    d = math.gcd(a[i], b[i])
    aa = a[i] // d
    bb = b[i] // d
    if aa < 0: # 非負数にする
        aa = -aa
        bb = -bb
    if (aa, bb) in dict:
        dict[(aa, bb)] += 1
    else:
        dict[(aa, bb)] = 1

bad = []
others = []
while dict:
    aa, bb = list(dict.keys())[0]
    if bb >= 0 and (bb, -aa) in dict:
        bad.append((dict[(aa, bb)], dict[(bb, -aa)]))
        del dict[(bb, -aa)]
    elif (-bb, aa) in dict:
        bad.append((dict[(aa, bb)], dict[(-bb, aa)]))
        del dict[(-bb, aa)]
    else:
        others.append(dict[(aa, bb)])
    del dict[(aa, bb)]

for (aa, bb) in dict:
    if dict[(aa, bb)] == 0: continue
    if (bb, -aa) in dict:
        bad.append((dict[(aa, bb)], dict[(bb, -aa)]))
        dict[(bb, -aa)] = 0
    elif (-bb, aa) in dict:
        bad.append((dict[(aa, bb)], dict[(-bb, aa)]))
        dict[(-bb, aa)] = 0
    else:
        others.append(dict[(aa, bb)])
    dict[(aa, bb)] = 0

ans = 1
for (x, y) in bad:
    ans = ans * (pow(2, x, p) + pow(2, y, p) - 1) % p
for z in others:
    ans = ans * pow(2, z, p) % p
ans -= 1
print(ans)

Submission status: Runtime Error

Solution code:
from math import gcd
from collections import Counter
mod = 10**9+7
def f(aai, bbi):
    gc = gcd(aai, bbi)
    a, b = aai // gc, bbi // gc
    if a < 0:
        a = -a
        b = -b
    return a, b

n= int(input())
aa = [0] * n
for i in range(n):
    ai, bi = map(int, input().split())
    aa[i] = f(ai, bi)

dic_ = Counter(aa)

cnt = 1
while len(dic_) > 0:
    k, v = dic_.popitem()
    ka , kb = k[0], k[1]
    if kb < 0:
        ka = -ka
        kb = -kb
    t = dic_.get((kb, -ka), 0)
    if t > 0:
        del dic_[(kb, -ka)]
        cnt *= ((2**v) + (2**t) - 1) % mod
    else:
        cnt *= (2**v) % mod
print((cnt+mod-1)%mod)

Submission status: Runtime Error

Solution code:
from math import gcd

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

t = []
d = {}
for a, b in AB:
    i = gcd(a, b)
    a //= i
    b //= i
    t.append((a, b))
    d.setdefault(a, {})
    d[a].setdefault(b, 0)
    d[a][b] += 1

used = set()
result = 1
for a, b in t:
    if (a, b) in used:
        continue
    used.add((a, b))
    if a == 0 and b == 0:
        i = d[a][b]
        result *= pow(2, i, 1000000007) - 1
        result %= 1000000007
    else:
        i = d[a][b]
        j, k, l = 0, 0, 0
        if -a in d and -b in d[-a]:
            j = d[-a][-b]
            used.add((-a, -b))
        if -b in d and a in d[-b]:
            k = d[-b][a]
            used.add((-b, a))
        if b in d and -a in d[b]:
            l = d[b][-a]
            used.add((b, -a))
        result *= pow(2, i + j, 1000000007) + pow(2, k + l, 1000000007) - 1
        result %= 1000000007
print(result - 1)

Submission status: Runtime Error

Solution code:
FAST_IO = 1
if FAST_IO:
    import io, sys, atexit
    rr = iter(sys.stdin.read().splitlines()).next
    sys.stdout = _OUTPUT_BUFFER = io.BytesIO()
    @atexit.register
    def write():
        sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
else:
    rr = raw_input
rri = lambda: int(rr())
rrm = lambda: map(int, rr().split())

####
from fractions import Fraction as Fra, gcd
from collections import Counter

def solve(N, A):
    MOD = 10 **9 + 7
    # Cant if dot product is 0
    count = Counter()
    for x, y in A:
        g = gcd(x, y)
        x //= g
        y //= g
        count[x, y] += 1

    # x,y = -y,x
    ans = 1
    for (x, y), c1 in count.iteritems():
        px, py = -y, x
        pg = gcd(px, py)
        px//=pg; py//=pg;
        c2 = count[px, py]
        if not c2:
            ans *= pow(2, c1, MOD)
            ans %= MOD
        elif (x,y) < (px,py):
            f = pow(2, c1, MOD) + pow(2, c2, MOD) - 1
            ans *= f
            ans %= MOD
    return (ans - 1) % MOD
    
    
N = rri()
A = [rrm() for _ in xrange(N)]
print solve(N, A)

Submission status: Runtime Error

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

MOD = 1000000007  # type: int

def func(b, w):
    return (pow(2, b, MOD) + pow(2, w, MOD) - 1) % MOD 

def solve(N: int, A: "List[int]", B: "List[int]"):
    from fractions import Fraction
    from collections import Counter
    C = [Fraction(a, b) for a, b in zip(A, B)]
    D = [-Fraction(b, a) for a, b in zip(A, B)]
    E = Counter(C)
    F = Counter(D)
    G = []
    used = set()
    for e, f in zip(E, F):
        if e in used or f in used:
            continue
        G.append((e, E[e], F[e]))
        used.add(e)
        used.add(f)
    ans = 1
    # print(G)
    for e, b, w in G:
        # print(b, w, func(b, w))
        ans = (ans * func(b, w)) % MOD
    return ans-1
        

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools
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))
    print(solve(N, A, B))

def test():
    import doctest
    doctest.testmod()

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

Submission status: Runtime Error

Solution code:
import bisect,sys
input = sys.stdin.readline
n=int(input())
ans=[0]*n
ans[0]=2
ans[-1]=1
mod=10**9+7
l=[0]*n
d={}
for i in range(n):
  a,b=map(float,input().split())
  x=a/b
  l[i]=x
l.sort()
z=bisect.bisect_right(l,0)
for i in range(1,z):
  ans[i]=(ans[i-1]*2)%mod
for i in range(z,n) :
  x=l[i]
  le=bisect.bisect_left(l,-1/x)
  r=bisect.bisect_right(l,-1/x)
  if le==r:
    ans[i]=(ans[i-1]*2)%mod
  else:
    z=bisect.bisect_left(l,x)   
    if i==z:
      ans[i]=ans[i-1]+2**(i-(r-le))
    else:
      ans[i]=ans[i-1]+ans[z]//2
print((ans[-1]-1)%mod)

Submission status: Runtime Error

Solution code:
n = int(input())
A_B_dict = {}
for i in range(n):
    a, b = map(int,input().split())
    temp = a/b
    if temp in A_B_dict:
        A_B_dict[temp] += 1
    else:
        A_B_dict[temp] = 1
net_dict = {}
if 0 in A_B_dict:
    net_dict[0] = 2**A_B_dict[0]
for i in A_B_dict:
    temp = -1/i
    if temp in A_B_dict:
        if i not in net_dict:
            net_dict[temp] = 2**A_B_dict[i] + 2**A_B_dict[temp] - 1
        else:
            pass
    else:
        net_dict[temp] = 2**A_B_dict[i]
ans = 1
for k in net_dict.values():
    ans = (ans*k)%1000000007
print((ans-1))

Submission status: Runtime Error

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

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

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

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

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

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


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

  
from collections import defaultdict


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

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

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

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

if cnt_00 >= 1:
    print(re)
ans += cnt_00 + ans * (cnt_a0 + cnt_b0)
print((ans - 1) % MOD)

Submission status: Runtime Error

Solution code:
import math
n = int(input())
x = [[0,0] for _ in range(n)]
h = 360
e = 360//h
c = 0
y = [[] for _ in range(h)]
mod = 10**9+7
for i in range(n):
  ai,bi = map(int,input().split())
  if ai == 0 and bi == 0:
    c += 1
  else:
    d = int(math.degrees(math.atan2(ai, bi))%360)
    j = d//e
    flag = True
    for ca in y[j]:
      if ai*ca[0][1] == bi*ca[0][0]:
        x[ca[1]][0] += 1
        flag = False
        break
    for ca in y[(j+180)%h]:
      if ai*ca[0][1] == bi*ca[0][0]:
        x[ca[1]][0] += 1
        flag = False
        break
    for ca in y[(j+90)%h]:
      if ai*ca[0][0]+bi*ca[0][1] == 0:
        x[ca[1]][1] += 1
        flag = False
        break
    for ca in y[(j-90)%h]:
      if ai*ca[0][0]+bi*ca[0][1] == 0:
        x[ca[1]][1] += 1
        flag = False
        break
    if flag:
      y[j].append([(ai,bi),i])
      x[i][0] = 1
ans = 1
for xi in x:
  if xi[0] == 0:
    if xi[1] != 0:
      ans = (ans*2**(xi[1]))%mod
  else:
    if xi[1] == 0:
      ans = (ans*2**(xi[0]))%mod
    else:
      ans = (ans*(2**(xi[0])+2**(xi[1])-1))%mod
ans += c-1
print(ans)

Submission status: Runtime Error

Solution code:
a = int(input())
resab = dict()
resba = dict()
res0 = 0
res0a = 0
res0b = 0
 
for i in range(a):
    ai, bi = [int(i) for i in input().split()]
    if ai != 0 and bi != 0:
        if ai/bi not in resab:
            resab[ai/bi] = 1
        else:
            resab[ai/bi] += 1
        if -bi/ai not in resba:
            resba[ -bi/ai] = 1
        else:
            resba[ -bi/ai] += 1
    else:
        if ai == 0 and bi == 0:
            res0 += 1
        elif ai == 0:
            res0a += 1
        elif bi == 0:
            res0b += 1
 

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

Submission status: Runtime Error

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
for i in range(N):
 A,B = map(int,input().split())
 x=Fraction(A,B)
 if A==0 and B==0:
  contnue
 elif A==0:
  c+=1
 elif B==0:
  d+=1
 else:
   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[-1/k],mod) -1)
   ans%=mod
 else:
   ans*=powmod(2,dic[k],mod)
   ans%=mod
for k in dica:
 if -1/k in dic:
  continue
 else:
  ans*=powmod(2,dica[k],mod)
  ans%=mod
ans*=(powmod(2,c,mod)+powmod(2,d,mod)-1)
ans%=mod
print(ans-1)

Submission status: Runtime Error

Solution code:
from collections import Counter
n = int(input())

N = 1000000007

def rate(a,b):
    r=1
    a1=a
    b1=b
    while r!=0:
        r=a1%b1
        a1=b1
        b1=r
    return (a//a1 , b//a1)

z =[]

for i in range(n):
    b , c = map(int, input().split())
    z.append(rate(b,c))

c = Counter(z)

k = list(c.keys())
v = list(c.values())


d=[]
e=0

for i in k:
    x,y=i
    if x<0:
        x*=-1
        y*=-1
    if (y*(-1),x) in k:
        t = (y*(-1),x)
        if not (c[t],c[i]) in d:
            d.append((c[i],c[t]))
    else:
        e+=c[i]

ans = 1
for i in d:
    x,y=i
    ans *= pow(2,x,N) + pow(2,y,N)-1
ans*=pow(2,e,N)
print(ans%N-1)

Submission status: Runtime Error

Solution code:
from sys import stdin, setrecursionlimit
from collections import deque


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())
        f = b / a
        if f < 0:
            m.append(-1 / f)
        elif f > 0:
            p.append(f)

    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 not (k in g_p):
            ans *= 2 ** g_m[k]
            ans %= mod
    print((ans - 1) % mod)


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

Submission status: Runtime Error

Solution code:
n = int(input())
A_B_dict = {}
for i in range(n):
    a, b = map(int,input().split())
    temp = a/b
    if temp in A_B_dict:
        A_B_dict[temp] += 1
    else:
        A_B_dict[temp] = 1
net_dict = {}
if 0 in A_B_dict:
    net_dict[0] = A_B_dict[0]
for i in A_B_dict:
    temp = -1/i
    if temp in A_B_dict:
        if i not in net_dict:
            net_dict[temp] = 2**A_B_dict[i] + 2**A_B_dict[temp] - 1
        else:
            pass
    else:
        net_dict[temp] = A_B_dict[i] + 1
ans = 1
for k in net_dict.values():
    ans = (ans*k)%1000000007
print((ans-1))

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = a; i < b; i ++)
#define FORS(i, a, b, c) for(int i = a; i < b; i += c)
#define FORN(i, a, b) for(int i = a; i <= b; i ++)
#define FORD(i, a, b) for(int i = a-1; i >= b; i --)
#define FORE(i, b) for(auto &i:b)
#define REP(i, b) FOR(i, 0, b)
#define REPN(i, b) FORN(i, 0, b)
#define SQ(i) (i*i)
#define ALL(a) a.begin(), a.end()
#define ALLA(a,n) a, a+n
#define SORT(a) sort(ALL(a))
#define SORTA(a, n) sort(ALLA(a, n))
#define REV(a) reverse(ALL(a))
#define REVA(a, n) reverse(ALLA(a, n))
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define IN(a, b) (a.find(b) != a.end())
#define BACK(a) a.back(); a.RB()
#define QBACK(a) a.top(); a.pop()
#define PRINT(a) FORE(i, a) cout << i << " "; cout << endl

#define PB  push_back
#define RB  pop_back
#define RF  pop_front
#define INS insert
#define F   first
#define S   second
#define UM  unordered_map
#define US  unordered_set
#define PQ  priority_queue

#define IO ios_base::sync_with_stdio(false); cin.tie(NULL)

typedef long long ll;
typedef unsigned long long ull;

typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<ll> vll;
typedef pair<int,int> pi;
typedef pair<double,double> pd;
typedef pair<ll,ll> pll;
typedef queue<int> qi;
typedef queue<double> qd;
typedef queue<ll> qll;
typedef US<int> si;
typedef US<double> sd;
typedef US<ll> sll;
typedef vector<vi> mi;
typedef vector<vd> md;
typedef vector<vll> mll;
typedef vector<pi> vpi;
typedef vector<pd> vpd;
typedef vector<pll> vpll;

const ll mod = 1e9+7;
ll pow(ll b, ll p){
  ll r = 1;
  while(p){
    if(p&1)r=r*b%mod;
    p>>=1; b=b*b%mod;
  }
  return r;
}
ll rev(ll a, ll b){
  return a*pow(b,mod-2)%mod;
}
ll gcd(ll a, ll b){
  return b ? gcd(b, a%b) : a;
}

int main(){
  IO; int N; cin >> N;
  map<pll, ll> freq;
  set<pll> vis;
  ll a, b;
  ll ans = 1;
  ll add = -1;
  while(N--){
    cin >> a >> b;
    if(!a&&!b){
      add ++;
      continue;
    }
    if(!a) b = 1;
    else if(!b) a = 1;
    else{ // b always +
      if(b<0)a*=-1,b*=-1;
      ll c = gcd(abs(a), abs(b));
      a /= c, b /= c;
    }
    freq[{a,b}]++;
  }
  FORE(i,freq){
    if(IN(vis,i.F)) continue;
    vis.INS(i.F);
    ll a = i.F.F, b = i.F.S;
    pll t = (a<=0?make_pair(b,-a):make_pair(-b,a));
    if(IN(freq,t)){
      vis.INS(t);
      ans=(pow(2ll,i.S)+pow(2ll,freq[t])-1)%mod*ans%mod;
    }else ans = ans*pow(2ll, i.S)%mod;
  }
  cout << (ans+add)%mod << endl;
}

Submission status: Runtime Error

Solution code:
import sys
from collections import Counter
from collections import deque
import math
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

mod=1000000007
n=int(input())
l1=[]
l2=[]
l0=0
for i in range(n):
    a,b=mp()
    if a*b>0:
        l1.append(a/b)
    elif a*b==0:
        l0+=1
    else:
        l2.append(-b/a)
c1=sorted(list(Counter(l1).most_common()),key=lambda x: x[0])
c2=sorted(list(Counter(l2).most_common()),key=lambda x: x[0])
c1.append((10**10, 1))
c2.append((10**10, 1))


ans=1
i=0
k=0
while i<len(c1)-1 or k<len(c2)-1:



    if c1[i][0]<c2[k][0]:
        ans*=pow(2,c1[i][1],mod)
        i+=1
    elif c1[i][0]>c2[k][0]:
        ans*=pow(2,c2[k][1],mod)
        k+=1
    else:
        ans*=(pow(2,c1[i][1],mod)+pow(2,c2[k][1],mod)-1)%mod
        i+=1
        k+=1
ans*=pow(2,l0,mod)
print((ans-1)%mod)

Submission status: Runtime Error

Solution code:
N = int(input())
AB = []
for i in range(N):
    Atmp,Btmp = list(map(int,input().split()))
    AB.append(Atmp/Btmp)

def power_func(a,n,p):
  bi=str(format(n,"b"))#2進表現に
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res

from collections import Counter
C = Counter(AB)

kaburi = []
forsum = []
for key in C:
    if key<0:
        if C[-1/key]!=0:
            kaburi.append([C[key],C[-1/key]])
            forsum.append(C[key]+C[-1/key])

p = 10**9+7

free = N-sum(forsum)
free2 = power_func(2,free,p)
L = len(kaburi)

out = 1
for i in range(len(kaburi)):
    X = kaburi[i][0]
    Y = kaburi[i][1]
    B = power_func(2,X,p)
    C = power_func(2,Y,p)
    out = out*((B+C-1)%p)
    out = out%p
print((out*free2-1)%p)

Submission status: Runtime Error

Solution code:
n = int(input())
A_B_dict = {}
for i in range(n):
    a, b = map(int,input().split())
    temp = a/b
    if temp in A_B_dict:
        A_B_dict[temp] += 1
    else:
        A_B_dict[temp] = 1
print(A_B_dict)
net_dict = {}
if 0 in A_B_dict:
    net_dict[0] = A_B_dict[0]
for i in A_B_dict:
    temp = -1/i
    if temp in A_B_dict:
        if i not in net_dict:
            net_dict[temp] = 2**A_B_dict[i] + 2**A_B_dict[temp] - 1
        else:
            pass
    else:
        net_dict[temp] = A_B_dict[i] + 1
print(net_dict)
ans = 1
for k in net_dict.values():
    ans = (ans*k)%1000000007
print((ans-1))

Submission status: Runtime Error

Solution code:
n = int(input())
mod = 10**9 + 7
cou = 0
pdic = {}
kan = []
for i in range(n):
    a , b = map(int,input().split())
    p = a/b
    q = -b/a
    if pdic.get(q,-1) != -1:
        kan[pdic[q]][1] += 1
    elif pdic.get(p,-1) == -1:
        pdic[p] = cou
        kan.append([1,0])
        cou += 1
    elif pdic.get(p,-1) != -1:
        kan[pdic[p]][0] += 1
        
ans = 1
for i in range(len(kan)):
    if kan[i][1] == 0:
        ans *= pow(2,kan[i][0],mod)
    elif kan[i][1] != 0:
        ans *= (pow(2,kan[i][0],mod) + pow(2,kan[i][1],mod)-1) % mod
    ans %= mod

print(ans-1)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = a; i < b; i ++)
#define FORS(i, a, b, c) for(int i = a; i < b; i += c)
#define FORN(i, a, b) for(int i = a; i <= b; i ++)
#define FORD(i, a, b) for(int i = a-1; i >= b; i --)
#define FORE(i, b) for(auto &i:b)
#define REP(i, b) FOR(i, 0, b)
#define REPN(i, b) FORN(i, 0, b)
#define SQ(i) (i*i)
#define ALL(a) a.begin(), a.end()
#define ALLA(a,n) a, a+n
#define SORT(a) sort(ALL(a))
#define SORTA(a, n) sort(ALLA(a, n))
#define REV(a) reverse(ALL(a))
#define REVA(a, n) reverse(ALLA(a, n))
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define IN(a, b) (a.find(b) != a.end())
#define BACK(a) a.back(); a.RB()
#define QBACK(a) a.top(); a.pop()
#define PRINT(a) FORE(i, a) cout << i << " "; cout << endl

#define PB  push_back
#define RB  pop_back
#define RF  pop_front
#define INS insert
#define F   first
#define S   second
#define UM  unordered_map
#define US  unordered_set
#define PQ  priority_queue

#define IO ios_base::sync_with_stdio(false); cin.tie(NULL)

typedef long long ll;
typedef unsigned long long ull;

typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<ll> vll;
typedef pair<int,int> pi;
typedef pair<double,double> pd;
typedef pair<ll,ll> pll;
typedef queue<int> qi;
typedef queue<double> qd;
typedef queue<ll> qll;
typedef US<int> si;
typedef US<double> sd;
typedef US<ll> sll;
typedef vector<vi> mi;
typedef vector<vd> md;
typedef vector<vll> mll;
typedef vector<pi> vpi;
typedef vector<pd> vpd;
typedef vector<pll> vpll;

const ll mod = 1e9+7;
ll pow(ll b, ll p){
  ll r = 1;
  while(p){
    if(p&1)r=r*b%mod;
    p>>=1; b=b*b%mod;
  }
  return r;
}
ll rev(ll a, ll b){
  return a*pow(b,mod-2)%mod;
}
ll gcd(ll a, ll b){
  return b ? gcd(b, a%b) : a;
}

int main(){
  IO; int N; cin >> N;
  map<pll, ll> freq;
  set<pll> vis;
  ll a, b;
  ll ans = 1;
  ll add = -1;
  while(N--){
    cin >> a >> b;
    if(!a&&!b){
      add ++;
      continue;
    }
    if(!a) b = 1;
    else if(!b) a = 1;
    else{ // b always +
      if(b<0)a*=-1,b*=-1;
      ll c = gcd(a, b);
      a /= c, b /= c;
    }
    freq[{a,b}]++;
  }
  FORE(i,freq){
    if(IN(vis,i.F)) continue;
    vis.INS(i.F);
    ll a = i.F.F, b = i.F.S;
    pll t = (a<=0?make_pair(b,-a):make_pair(-b,a));
    if(IN(freq,t)){
      vis.INS(t);
      ans=(pow(2ll,i.S)+pow(2ll,freq[t])-1)%mod*ans%mod;
    }else ans = ans*pow(2ll, i.S)%mod;
  }
  cout << (ans+add)%mod << endl;
}

Submission status: Runtime Error

Solution code:
import sys
from math import gcd
from collections import Counter
# # def input(): return sys.stdin.readline().rstrip()
# # input = sys.stdin.readline
input = sys.stdin.buffer.readline
# sys.setrecursionlimit(10 ** 7)
MOD = 1000000007

N = int(input())
ab = []
for i in range(N):
    a,b = map(int, input().split())
    gcd_ab = gcd(a,b)
    a //= gcd_ab
    b //= gcd_ab
    if a<0:     # aは常に正にする
        a *= -1
        b *= -1
    ab.append((a,b))
Cnt = Counter(ab)
# print(Cnt)

ans = 1
done = set()
for (a, b), c in Cnt.items():
    # print(a,b,c)
    if (a,b) in done: continue
    if b < 0:
        if (-b, a) in Cnt.keys():
            ans *= (pow(2,Cnt[(a,b)],MOD)-1) + (pow(2,Cnt[(-b,a)],MOD)-1) + 1
            ans %= MOD
            done.add((a,b))
            done.add((-b,a))
        else:
            ans *= pow(2,Cnt[(a,b)],MOD)
            ans %= MOD
            done.add((a,b))
    else:
        if (b, -a) in Cnt.keys():
            ans *= (pow(2,Cnt[(a,b)],MOD)-1) + (pow(2,Cnt[(b,-a)],MOD)-1) + 1
            ans %= MOD
            done.add((a,b))
            done.add((b,-a))
        else:
            ans *= pow(2,Cnt[(a,b)],MOD)
            ans %= MOD
            done.add((a,b))

print(ans-1)

Submission status: Runtime Error

Solution code:
import math
n = int(input())
a = [0] * n;  b = [0] * n;
for i in range(n):
    a[i], b[i] = [int(x) for x in input().split()]
p = 10 ** 9 + 7

d = [0] * n
dict = {}
for i in range(n):
    d[i] = math.gcd(a[i], b[i])
    aa = a[i] // d[i]
    bb = b[i] // d[i]
    if aa < 0: # 非負数にする
        aa = -aa
        bb = -bb
    if (aa, bb) in dict:
        dict[(aa, bb)] += 1
    else:
        dict[(aa, bb)] = 1

bad = []
others = []
while dict:
    aa, bb = list(dict.keys())[0]
    if bb >= 0 and (bb, -aa) in dict:
        bad.append((dict[(aa, bb)], dict[(bb, -aa)]))
        del dict[(bb, -aa)]
    elif (-bb, aa) in dict:
        bad.append((dict[(aa, bb)], dict[(-bb, aa)]))
        del dict[(-bb, aa)]
    else:
        others.append(dict[(aa, bb)])
    del dict[(aa, bb)]

ans = 1
for (x, y) in bad:
    ans = ans * (pow(2, x, p) + pow(2, y, p) - 1) % p
for z in others:
    ans = ans * pow(2, z, p) % p
ans -= 1
print(ans)

Submission status: Runtime Error

Solution code:
import sys
from collections import Counter
from collections import deque
import math
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

mod=1000000007
n=int(input())
l1=[]
l2=[]
l0=0
for i in range(n):
    a,b=mp()
    if a*b>0:
        l1.append(a/b)
    elif a*b==0:
        l0+=1
    else:
        l2.append(-b/a)
c1=sorted(list(Counter(l1).most_common()),key=lambda x: x[0])
c2=sorted(list(Counter(l2).most_common()),key=lambda x: x[0])
c1.append((10**10, 1))
c2.append((10**10, 1))


ans=1
i=0
k=0
while i<len(c1)-1 or k<len(c2)-1:



    if c1[i][0]<c2[k][0]:
        ans*=pow(2,c1[i][1],mod)
        i+=1
    elif c1[i][0]>c2[k][0]:
        ans*=pow(2,c2[k][1],mod)
        k+=1
    else:
        ans*=(pow(2,c1[i][1],mod)+pow(2,c2[k][1],mod)-1)%mod
        i+=1
        k+=1

print((ans-1)%mod)

Submission status: Runtime Error

Solution code:
n=int(input())
d={}
for i in range(n):
    a,b=map(int,input().split())
    if a==0 and b==0:
        if [0,0] not in d:
            d[[0,0]]=[1,0]
        else:
            d[[0,0]][0]+=1
    elif a==0:
        if 0 not in d:
            d[0]=[1,0]
        else:
            d[0][0]+=1
    elif b==0:
        if 0 not in d:
            d[0]=[0,1]
        else:
            d[0][1]+=1
    else:
        if a/b not in d and -b/a not in d:
            d[a/b]=[1,0]
        elif a/b in d:
            d[a/b][0]+=1
        else:
            d[-b/a][1]+=1
sq=[1]*(n+1)
for i in range(n):
    sq[i+1]=2*sq[i]%1000000007

ans=1
r=list(d.values())
for i in range(len(r)):
    ans*=(sq[r[i][0]]+sq[r[i][1]]-1)%1000000007
print(ans-1)

Submission status: Runtime Error

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



import bisect
from math import gcd
n = int(input())
l = [None] * n
for i in range(n):
    a,b = map(int, input().split())
    g = gcd(a,b)
    l[i] = (a//g, b//g)

l.sort()
M = 1000000007
seen = [False] * n
vals = []

def sub(item):
    item1 = (item[1], -item[0])
    item2 = (-item[1], item[0])
    tmp = None
    count = 0
    li = bisect.bisect_left(l, item1)
    ri = bisect.bisect_right(l, item1)
    count += (ri-li)
    for v in range(li, ri):
        seen[v] = True
    if ri>li:
        tmp = l[li]
        
    li = bisect.bisect_left(l, item2)
    ri = bisect.bisect_right(l, item2)
    count += (ri-li)
    for v in range(li, ri):
        seen[v] = True
    if ri>li:
        tmp = l[li]
    
    return count, tmp

for i,item in enumerate(l):
    if seen[i]:
        continue
    count,tmp = sub(item)
    if count>0:
        count2, tmp = sub(tmp)
        vals.append((pow(2,count,M)+pow(2,count2,M)-1)%M)
    else:
        vals.append(2)
ans = 1
for v in vals:
    ans *= v
    ans %= M
print(ans-1 if len(vals)>=2 else ans)

Submission status: Runtime Error

Solution code:
from collections import Counter
from math import gcd
import sys
input = sys.stdin.readline
n = int(input())
same, diff, zero_a, zero_b = 0, 0, 0, 0
same_cnt = Counter()
diff_cnt = Counter()

for _ in range(n):
    a, b = map(int, input().split())
    x = gcd(a, b)
    a, b = a // x, b // x
    if a == b == 0:
        continue
    elif a == 0:
        zero_a += 1
    elif b == 0:
        zero_b += 1
    elif a * b > 0:
        same += 1
        same_cnt[(abs(a), abs(b))] += 1
    else:
        diff += 1
        diff_cnt[(abs(a), -abs(b))] += 1


ans = 1
mod = 10 ** 9 + 7

for (a, b) in diff_cnt.keys():
    s = same_cnt[(-b, a)]
    d = diff_cnt[(a, b)]
    if s > 0:
        same -= s
        diff -= d
        ans = ans * (pow(2, s, mod) + pow(2, d, mod) - 1) % mod

ans = ans * pow(2, same + diff, mod) % mod

ans = ans * (pow(2, zero_a, mod) + pow(2, zero_b, mod) - 1) - 1
print(ans % mod)