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 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 (a,b) == (0,0):
        done.add((a,b))
        continue
    elif b < 0:
        if (-b, a) in Cnt.keys():
            ans *= (pow(2,c,MOD)-1) + (pow(2,Cnt[(-b,a)],MOD)-1) + 1
            ans %= MOD
            done.add((a,b))
            done.add((-b,a))
        else:
            ans *= pow(2,c,MOD)
            ans %= MOD
            done.add((a,b))
    else:
        if (b, -a) in Cnt.keys():
            ans *= (pow(2,c,MOD)-1) + (pow(2,Cnt[(b,-a)],MOD)-1) + 1
            ans %= MOD
            done.add((a,b))
            done.add((b,-a))
        else:
            ans *= pow(2,c,MOD)
            ans %= MOD
            done.add((a,b))
# print(done)
if (0,0) not in Cnt:
    ans -= 1
    ans % MOD
print(ans)

Submission status: Runtime Error

Solution code:
def main():
    import math
    import collections
    N = int(input())

    mod = 10**9+7
    AB = [tuple(map(int, input().split())) for i in range(N)]

    d = collections.defaultdict(set)
    i = 0
    ab = []
    for a, b in AB:
        g = math.gcd(a, b)
        a = a // g
        b = b // g
        # d[(a, b)] += 1
        if a > 0 and b < 0:
            a = -a
            b = -b
        d[(a, b)].add(i)
        ab.append((a, b))
        i += 1

    ans = 0
    r = set()

    dd = [1]
    for i in range(1, N+1):
        dd.append(dd[i-1]*2 % mod)

    r = set()
    ans = 1
    for (a, b) in d:
        if (a, b) in r:
            continue
        l1 = len(d[(a, b)])

        tmp = dd[l1]
        s = set()
        if (-b, a) in d:
            s |= d[(-b, a)]
        if (b, -a) in d:
            s |= d[(b, -a)]
        l2 = len(s)
        if l2:
            ans *= tmp + dd[l2] - 1
            N -= l1 + l2
            ans %= mod

            r.add((-b, a))
            r.add((b, -a))
        else:
            continue
    if N:
        ans *= dd[N]
    ans -= 1

    print(ans % mod)


main()

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())
if n==1:
    print(1)
    exit()
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)
        i+=1
        k+=1
ans*=pow(2,l0,mod)
print((ans-1)%mod)

Submission status: Runtime Error

Solution code:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res

def gcd(x, y):
    if x < y:
        x = x ^ y
        y = x ^ y
        x = x ^ y
    div = x % y
    while div != 0:
        x = y
        y = div
        div = x % y
    return y


N=II()
MP1={}
A0 = 0
B0 = 0
AB0 = 0
RES=1
for i in range(N):
    A, B = LI()
    G = gcd(abs(A),abs(B))
    A //= G
    B //= G
    if A*B != 0:
        v = (abs(A), abs(B), A*B > 0)
        if not v in MP1:
            MP1[v] = 1
        else:
            MP1[v] += 1

    if A == 0 and B != 0: A0 += 1
    if A != 0 and B == 0: B0 += 1

print(MP1)

VIS = set()
for (vv, n) in MP1.items():
    # print(vv, n)
    (A, B, isPos) = vv
    v = (B, A, not isPos)
    if not v in VIS and not vv in VIS:
        VIS.add(v)
        VIS.add(vv)
        if v in MP1:
            m = MP1[v]
            RES = (RES*POW(2, n))%DVSR + (RES*POW(2, m))%DVSR - RES
            RES %= DVSR
        else:
            RES *= POW(2, n)
            RES %= DVSR
    # print(RES)

if A0 and B0:
    RES = (RES*POW(2, A0))%DVSR + (RES*POW(2, B0))%DVSR
elif A0:
    RES = RES*POW(2, A0)%DVSR
elif B0:
    RES = RES*POW(2, B0)%DVSR

print(RES-1)

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())
if n==1:
    print(1)
    exit()
l1=[]
l2=[]
l0=0
for i in range(n):
    
    a,b=mp()
    c=math.gcd(a,b)
    if a*b>0:
        l1.append((a/b,abs(a)//c,abs(b)//c))
    elif a*b==0:
        l0=1
    else:
        l2.append((-b/a,abs(b)//c,abs(a)//c))
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))

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



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

Submission status: Runtime Error

Solution code:
def main():
    import math
    import collections
    N = int(input())

    mod = 10**9+7
    AB = [tuple(map(int, input().split())) for i in range(N)]

    d = collections.defaultdict(set)
    i = 0
    ab = []
    for a, b in AB:
        g = math.gcd(a, b)
        a = a // g
        b = b // g
        # d[(a, b)] += 1
        if a > 0 and b < 0:
            a = -a
            b = -b
        d[(a, b)].add(i)
        ab.append((a, b))
        i += 1

    ans = 0
    r = set()

    dd = [1]
    for i in range(1, N+1):
        dd.append(dd[i-1]*2 % mod)

    r = set()
    ans = 1
    for (a, b) in d:
        if (a, b) in r:
            continue
        l1 = len(d[(a, b)])

        tmp = dd[l1]
        s = set()
        if (-b, a) in d:
            s |= d[(-b, a)]
        if (b, -a) in d:
            s |= d[(b, -a)]
        l2 = len(s)
        if l2:
            ans *= tmp + dd[l2] - 1
            N -= l1 + l2
            ans %= mod

            r.add((-b, a))
            r.add((b, -a))
        else:
            continue
    if N:
        ans *= dd[N]*2
    ans -= 1

    print(ans % mod)


main()

Submission status: Runtime Error

Solution code:
#include <algorithm>
#include <iostream>
#include <string>
#include <random>
#include <cassert>
#include <cstring>
#include <chrono>
#include <set>
#include <map>

using namespace std;

typedef long long ll;

const ll mod = 1000 * 1000 * 1000 + 7;

ll GCD(ll a, ll b) {
  if (a < 0) a *= -1;
  if (b < 0) b *= -1;
  if (a == 0) return b;
  return GCD(b % a, a);
}

void Normalize(ll& x, ll& y) {
  ll g = GCD(x, y);
  x /= g;
  y /= g;
  if (make_pair(x, y) < make_pair(-x, -y)) {
    x = -x;
    y = -y;
  }
}

ll Get(const vector<pair<int, int>>& v) {
  int min1 = mod;
  int min2 = mod;
  ll pow1 = 1;
  ll pow2 = 1;
  for (auto p : v) {
    if (p.first == 0) {
      min1 = min(min1, p.second);
      pow1 = pow1 * 2 % mod;
    } else {
      min2 = min(min2, p.second);
      pow2 = pow2 * 2 % mod;
    }
  }
  ll result = (pow1 + pow2 - 1 + mod) % mod;
  if (min1 > min2) result = 1;
  return result;
}

int main()
{
  int n;
  cin >> n;
  vector<ll> x, y;
  ll add = 0;
  for (int i = 0; i < n; ++i) {
    ll a, b;
    cin >> a >> b;
    if (a == 0 && b == 0) {
      add++;
      continue;
    }
    x.push_back(a);
    y.push_back(b);
  }

  n = x.size();

  map<pair<ll, ll>, vector<pair<int, int>>> m;

  for (int i = 0; i < n; ++i) {
    ll cx = x[i];
    ll cy = y[i];

    Normalize(cx, cy);
    m[{cx, cy}].push_back({0, i});

    cx = y[i];
    cy = -x[i];
    
    Normalize(cx, cy);
    m[{cx, cy}].push_back({1, i});
  }

  ll result = 1;
  for (auto it : m) {
    auto v = it.second;
    result = result * Get(v) % mod;
  }

  result = max<ll>(0, result - 1);
  cout << result + add << endl;

  return 0;
}

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 (a,b) == (0,0):
        done.add((a,b))
        continue
    elif b < 0:
        if (-b, a) in Cnt.keys():
            ans *= (pow(2,c,MOD)-1) + (pow(2,Cnt[(-b,a)],MOD)-1) + 1
            ans %= MOD
            done.add((a,b))
            done.add((-b,a))
        else:
            ans *= pow(2,c,MOD)
            ans %= MOD
            done.add((a,b))
    else:
        if (b, -a) in Cnt.keys():
            ans *= (pow(2,c,MOD)-1) + (pow(2,Cnt[(b,-a)],MOD)-1) + 1
            ans %= MOD
            done.add((a,b))
            done.add((b,-a))
        else:
            ans *= pow(2,c,MOD)
            ans %= MOD
            done.add((a,b))
# print(done)
ans -= 1
ans % MOD
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
MOD = 1000000007
s, zero = {}, 0

for _ in range(N):
    A, B = map(int, input().split())
    if A == 0 and B == 0:
        zero += 1
    elif B == 0:
        key = 
        if s.get(float('inf')) == None:
            s[float('inf')] = 1
        else:
            s[float('inf')] += 1
    else:
        if s.get(A/B) == None:
            s[A/B] = 1
        else:
            s[A/B] += 1

f, ans = 0, 1
while len(s) > 0:
    k1, v1 = s.popitem()
    if k1 == 0:
        key = float('inf')
    else:
        key = -1/k1
    if key in s.keys():
        v2 = s.pop(key)
        Cv1, Cv2 = pow(2, v1, MOD), pow(2, v2, MOD)     # pow(2, n, MOD) は二項定理による組み合わせの総和
        C = ((Cv1 + Cv2) % MOD + (MOD - 1)) % MOD
        ans = (ans * C) % MOD
    else:
        f += v1

ans = ((ans * pow(2, f, MOD)) % MOD  + (MOD - 1)) % MOD
ans = (ans + zero) % MOD
print(ans)

Submission status: Runtime Error

Solution code:
from sys import stdin
from sys import setrecursionlimit
from queue import deque
import math
setrecursionlimit(10 ** 7)

mod = 10**9+7

dic = {}
dic2 = {}

n = int(stdin.readline().rstrip())
for i in range(n):
    a,b = map(int,stdin.readline().rstrip().split())
    if a == 0 or b == 0:
        if 0 not in dic:
            dic["0"] = 1
            dic2["0"] = 1
        else:
            dic["0"] += 1
            dic2["0"] += 1
    if str(-a/b) in dic:
        dic[str(-a/b)] += 1
    else:
        dic[str(-a/b)] = 1
    if str(b/a) in dic2:
        dic2[str(b/a)] += 1
    else:
        dic2[str(b/a)] = 1

point = 0

for i,j in dic.items():
    if i in dic2:
        point += j*dic2[i]
        point %= mod

point //= 2

print(math.factorial(n)-point)

Submission status: Runtime Error

Solution code:
import math 

MOD = 10**9 + 7
N = int(input())
ABC = []
zero_cases = 0
for i in range(N):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zero_cases = 1
    elif a * b >=0 and a != 0:
        ABC.append([ math.atan2(abs(b),abs(a)), abs(a), abs(b),1])
    else:
        ABC.append([math.atan2(abs(a),abs(b)), abs(b), abs(a), -1])
ABC.sort()
current_arg = ABC[-1][0]
group = []
daiich = 0
daini = 0
while ABC:
    current = ABC.pop()
    if current[0] == current_arg:
        if current[3]==1:
            daiich += 1
        else:
            daini += 1
    else:
        group += [[daiich, daini]]
        daiich = 0
        daini = 0
        if current[3]==1:
            daiich += 1
        else:
            daini += 1
        if ABC:
            current_arg = current[0]
else:
    group += [[daiich, daini]]
    daiich = 0
    daini = 0

ans = 1 + zero_cases
for u, v in group:
    ans *= (2**u + 2**v -1)
    ans %= MOD
print(ans-1)

Submission status: Runtime Error

Solution code:
import math
import bisect
N = int(input())
atans =  [0 for _ in range(N)]
for i in range(N):
  A, B = map(int, input().split())
  if A == 0:
    atans[i] = 90
  else:
    atans[i] = math.degrees(math.atan(A/B))

atans.sort()
index0 = bisect.bisect_left(atans, 0)
if (index0==0) or (index0==N):
  print(pow(2, N, 1000000007) -1)
  exit()

left = atans[:index0]
right = atans[index0:]
ans = 1

lenleft = index0
lenright = N - index0
now = -90
for i in range(index0):
  if left[i]==now:
    continue
  now = left[i]
  target = now+90
  same1 = bisect.bisect_right(right, target) - bisect.bisect_left(right, target)
  
  if same1 >= 1:
    lenright -= same1
    same2 = bisect.bisect_right(left, now) - bisect.bisect_left(left, now)
    ans = ans * (pow(2,same1,1000000007)+pow(2,same2,1000000007)-1) %1000000007
  else:
    ans = ans * 2 %1000000007

ans = (ans * pow(2, lenright, 1000000007) -1) % 1000000007
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

import numpy as np

N = int(input())
P = [[int(i) for i in input().split()] for _ in range(N)]


Pmat = np.matrix(P)


badmat = Pmat@Pmat.T
badmat = np.where(badmat == 0)

graph = [deque([]) for _ in range(N)]
for i in range(N):
    graph[i].extend(badmat[1][badmat[0] == i])

visit = [-1] * (N)

# 深さ優先探索


def dfs(v):
    s = 1
    stack = [v]
    visit[v] = 1
    while stack:
        v = stack[-1]
        if graph[v]:
            w = graph[v].popleft()
            if visit[w] == -1:
                visit[w] = 1
                s += 1
                stack.append(w)
        else:
            stack.pop()
    return s


ans = []
# 孤立している頂点対策
for i in range(N):
    if visit[i] == -1:
        ans.append(dfs(i))


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

kotae = 0
for a in ans:
    kotae += power_func(2, a, 1000000007)
    kotae = kotae % 1000000007
print(kotae - 1)

Submission status: Runtime Error

Solution code:
import numpy as np
import itertools

n = int(input())
ab = [input().split() for l in range(n)]
npab=np.array(ab, dtype='float64')

#print (n)
#print (npab)

nptable = np.zeros((n,n))
for i in range(0,n):
  for j in range(i+1,n):
    nptable[i,j]=npab[i,0]*npab[j,0]+npab[i,1]*npab[j,1]

#print (nptable)

count=n

for i in range(2,n+1):
  base = list(itertools.combinations(range(0,n),i))
#  print (base)

  for j in base:
    flag=1
    base2=list(itertools.combinations(j,2))
    for k in base2:
      if (nptable[k[0],k[1]] == 0 and flag == 1): flag=0
#      print (j, j[k],j[k+1], nptable[j[k],j[k+1]], flag)
#    if (nptable[j[0],j[ll-1]] == 0 and flag == 1): flag=0
        
    if (flag == 1): count=count+1
    
print (count % 1000000007)

Submission status: Runtime Error

Solution code:
import math 

MOD = 10**9 + 7
N = int(input())
ABC = []
zero_cases = 1
for i in range(N):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zero_cases = 2
    elif a * b >=0 and a != 0:
        ABC.append([ math.atan2(abs(b),abs(a)), abs(a), abs(b),1])
    else:
        ABC.append([math.atan2(abs(a),abs(b)), abs(b), abs(a), -1])
ABC.sort()
current_arg = ABC[-1][0]
current_x = ABC[-1][1]
current_y = ABC[-1][2]
group = []
daiich = 0
daini = 0
while ABC:
    current = ABC.pop()
    di = {}
    if current[0] == current_arg:
        if current[3]==1:
            daiich += 1
        else:
            daini += 1
    else:
        group += [[daiich, daini]]
        daiich = 0
        daini = 0
        if current[3]==1:
            daiich += 1
        else:
            daini += 1
        if ABC:
            current_arg = current[0]
            current_x = current[1]
            current_y = current[2]
else:
    group += [[daiich, daini]]
    daiich = 0
    daini = 0

ans = zero_cases
for u, v in group:
    ans *= (2**u + 2**v -1)
    ans %= MOD
print(ans-1)

Submission status: Runtime Error

Solution code:
import numpy as np
import itertools

n = int(input())
ab = [input().split() for l in range(n)]
npab=np.array(ab, dtype='int64')

#print (n)
#print (npab)

nptable = np.zeros((n,n))
for i in range(0,n):
  for j in range(i+1,n):
    nptable[i,j]=npab[i,0]*npab[j,0]+npab[i,1]*npab[j,1]

#print (nptable)

count=n

for i in range(2,n+1):
  base = list(itertools.combinations(range(0,n),i))
#  print (base)

  for j in base:
    flag=1
    base2=list(itertools.combinations(j,2))
    for k in base2:
      if (nptable[k[0],k[1]] == 0 and flag == 1): flag=0
#      print (j, j[k],j[k+1], nptable[j[k],j[k+1]], flag)
#    if (nptable[j[0],j[ll-1]] == 0 and flag == 1): flag=0
        
    if (flag == 1): count=count+1
    
print (count % 1000000007)

Submission status: Runtime Error

Solution code:
def main():
    import math
    import collections
    N = int(input())

    # def cmb(n, r, mod):
    #     if (r < 0 or r > n):
    #         return 0
    #     r = min(r, n-r)
    #     return g1[n] * g2[r] * g2[n-r] % mod

    mod = 10**9+7
    # g1 = [1, 1]  # 元テーブル
    # g2 = [1, 1]  # 逆元テーブル
    # inverse = [0, 1]  # 逆元テーブル計算用テーブル

    # for i in range(2, N + 1):
    #     g1.append((g1[-1] * i) % mod)
    #     inverse.append((-inverse[mod % i] * (mod//i)) % mod)
    #     g2.append((g2[-1] * inverse[-1]) % mod)

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

    # d = collections.defaultdict(int)
    d = collections.defaultdict(set)
    # d2 = collections.defaultdict(int)
    i = 0
    ab = []
    for a, b in AB:
        g = math.gcd(a, b)
        a = a // g
        b = b // g
        # d[(a, b)] += 1
        if a > 0 and b < 0:
            a = -a
            b = -b
        d[(a, b)].add(i)
        ab.append((a, b))
        i += 1

    ans = 0
    r = set()

    dd = [1]
    for i in range(1, N):
        dd.append(dd[i-1]*2 % mod)

    r = set()
    ans = 1
    for (a, b) in d:
        if (a, b) in r:
            continue
        l1 = len(d[(a, b)])
        tmp = dd[l1]
        s = set()
        if (-b, a) in d:
            s |= d[(-b, a)]
        if (b, -a) in d:
            s |= d[(b, -a)]
        l2 = len(s)
        if l2:
            ans *= tmp + dd[l2] - 1
            N -= l1 + l2
            ans %= mod

            r.add((-b, a))
            r.add((b, -a))
        else:
            continue
    if N:
        ans *= dd[N-1]*2
    ans -= 1

    print(ans % mod)


main()

Submission status: Runtime Error

Solution code:
N = int(input())
Y = list()
for i in range(N):
    a,b = map(int,input().split())
    Y.append([a,b])
NGLIST = 0
MOD = 1000000007
  
for i in range(N-1):
    for j in range(i+1,N):
        if Y[i][0] * Y[j][0] + Y[i][1] * Y[i][1] == 0:
            NGLIST += 1

def modinv(a,mod):
    b, u, v = mod, 1, 0
    while b > 0:
        t = a // b
        a -= t * b
        a, b = b , a
        u -= t * v
        u, v = v, u
    u = u % mod
    if u < 0: 
        u += mod
    return u
modlist = [1]
invmodlist = [1]
for i in range(1,N+1):
    tmp = modlist[-1] * i % MOD
    modlist.append(tmp)
    tmp2 = modinv(i,MOD)
    tmp2 = invmodlist[-1] * tmp2 % MOD
    invmodlist.append(tmp2)
ret = 0
for i in range(1,N+1):
    if i == 1:
        ret += N 
    elif i == 2:
        tmp = (modlist[N] * modlist[N-1] % MOD) * invmodlist[2] * invmodlist[1] % MOD
        ret += tmp
    else:
        N2, i2 = N - 2, i - 2
        tmp = ((modlist[N]) * invmodlist[i] % MOD )* invmodlist[N-i] % MOD
        tmp2 = ((modlist[N2]) * invmodlist[i2] % MOD )* invmodlist[N2-i2] % MOD
        tmp = (tmp - tmp2) % MOD
        ret += tmp
    ret = ret % MOD
return ret

Submission status: Runtime Error

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

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

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

for i in d.keys():
    i0, i1 = map(int,i.split())
    if str(i1)+" "+str(-i0) in d:
        if d[i] == 0:
            continue
        aaa = (twoxxn(d[str(i1)+" "+str(-i0)],mod)+twoxxn(d[i],mod)-1)%mod
        ans = (ans*aaa)%mod
        d[str(i1)+" "+str(-i0)] = 0
    elif str(-i1)+" "+str(i0) in d:
        if d[i] == 0:
            continue
        aaa = (twoxxn(d[str(-i1)+" "+str(i0)],mod)+twoxxn(d[i],mod)-1)%mod
        ans = (ans*aaa)%mod
        d[str(-i1)+" "+str(i0)] = 0
    else:
        ans = (ans*twoxxn(d[i],mod))%mod

if ans == 1:
    print(1)
    exit()
ans = (ans-1)%mod
print(ans)

Submission status: Runtime Error

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations, combinations_with_replacement
from heapq import heappop, heappush
from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

def main():
    n = inp()
    dic = defaultdict(int)
    dic1 = defaultdict(int)
    for _ in range(n):
        a,b = inpm()
        if a != 0 and b == 0:
            a = 1
        elif a == 0 and b != 0:
            b = 1
        else:
            if not (a==0 and b==0):
                m = gcd(a,b)
                a //= m
                b //= m
        if a < 0 and b < 0:
            a = -a
            b = -b
        if a < 0 and b > 0:
            a = -a
            b = -b
        index = ' '.join([str(a),str(b)])
        dic[index] += 1
        dic1[index] += 1
    ans = 1
    dic2 = defaultdict(int)
    for e in dic:
        a,b = map(int,e.split())
        if a == 0 or b == 0:
            continue
        flag = 0
        if a > 0 and b > 0:
            rev = ' '.join([str(b),str(-a)])
        else:
            rev = ' '.join([str(-b),str(a)])
        if dic1[rev] > 0 and dic2[rev] == 0:
            dic2[rev] = 1
            dic2[e] = 1
            flag = 1
        if flag:
            continue
        n1 = pow(2,dic[e],mod)
        n2 = pow(2,dic1[rev],mod)
        if n1 == 0:
            ans *= n2
        elif n2 == 0:
            ans *= n1
        else:
            ans *= (n1+n2-1)
        ans %= mod
    if dic['1 0'] and dic['0 1']:
        num = (pow(2,dic['1 0'],mod)+pow(2,dic['0 1'],mod)-1)
        num %= mod
    elif dic['1 0']:
        num = pow(2,dic['1 0'],mod)
        num %= mod
    elif dic['0 1']:
        num = pow(2,dic['0 1'],mod)
        num %= mod
    if num != 0:
        ans *= num
        ans %= mod
    print(ans-1+dic['0 0'])
    
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def main():
    import math
    import collections
    N = int(input())

    # def cmb(n, r, mod):
    #     if (r < 0 or r > n):
    #         return 0
    #     r = min(r, n-r)
    #     return g1[n] * g2[r] * g2[n-r] % mod

    mod = 10**9+7
    # g1 = [1, 1]  # 元テーブル
    # g2 = [1, 1]  # 逆元テーブル
    # inverse = [0, 1]  # 逆元テーブル計算用テーブル

    # for i in range(2, N + 1):
    #     g1.append((g1[-1] * i) % mod)
    #     inverse.append((-inverse[mod % i] * (mod//i)) % mod)
    #     g2.append((g2[-1] * inverse[-1]) % mod)

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

    # d = collections.defaultdict(int)
    d = collections.defaultdict(set)
    # d2 = collections.defaultdict(int)
    i = 0
    ab = []
    for a, b in AB:
        g = math.gcd(a, b)
        a = a // g
        b = b // g
        # d[(a, b)] += 1
        if a > 0 and b < 0:
            a = -a
            b = -b
        d[(a, b)].add(i)
        ab.append((a, b))
        i += 1

    ans = 0
    r = set()

    dd = [1]
    for i in range(1, N):
        dd.append(dd[i-1]*2 % mod)

    r = set()
    ans = 1
    for (a, b) in d:
        if (a, b) in r:
            continue
        l1 = len(d[(a, b)])
        tmp = dd[l1]
        s = set()
        if (-b, a) in d:
            s |= d[(-b, a)]
        if (b, -a) in d:
            s |= d[(b, -a)]
        l2 = len(s)
        if l2:
            ans *= tmp + dd[l2] - 1
            N -= l1 + l2
            ans %= mod

            r.add((-b, a))
            r.add((b, -a))
        else:
            continue

    ans *= dd[N]
    ans -= 1

    print(ans % mod)


main()

Submission status: Runtime Error

Solution code:
N = int(input())
data = []
for _ in range(N):
  data.append([int(v) for v in input().split(" ")])

count = 0

def check_ab(bit, j):
  if len(bit) == 0:
    return True
  
  for i in range(len(bit)):
    if bit[i] == 0:
      continue
    if data[i][0] * data[j][0] + data[i][1] * data[j][1] == 0:
      return False
    
  return True

def dfs(bit):
  global count
  if (len(bit) == N):
    if sum(bit) > 0:
      count = (count + 1) % 1000000007
    return
  
  else:
    c = 0
    bit.append(c)
    dfs(bit)
    bit.pop()
    
    c = 1
    if check_ab(bit, len(bit)):
      bit.append(c)
      dfs(bit)
      bit.pop()
        
dfs([])
print(count)

Submission status: Runtime Error

Solution code:
from collections import Counter
import sys
input = sys.stdin.buffer.readline

N = int(input())

def gcd(n, m):
    if m == 0:
        return n
    return gcd(m, n % m)

def make(a, b):
    s = 1 if a * b >= 0 else -1
    a, b = abs(a), abs(b)

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

    return (a, b, s)

ABS = Counter([make(*map(int, input().split())) for _ in range(N)])
K = list(ABS.keys())

ans = 1
MOD = 10**9 + 7

for a, b, s in K:
    p = ABS[(a, b, s)]
    n = ABS[(b, a, -s)]

    ABS[(a, b, s)] = 0
    ABS[(b, a, -s)] = 0

    cnt = pow(2, p, MOD) + pow(2, n, MOD) - 1
    ans = (ans * cnt) % MOD

print((ans - 1) % MOD)

Submission status: Runtime Error

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

mod=10**9+7
n=int(input())
fact=[1]
revfact=[1]
for i in range(1,2*10**5+1):
  fact.append((fact[-1]*i)%mod)
  revfact.append(pow(fact[-1],mod-2,mod))
dic={}
cnt=0
for _ in range(n):
  a,b=map(int,input().split())
  if a!=0 and b!=0:
    g=gcd(abs(a),abs(b))
    if a*b>0:
      if (abs(a)//g,abs(b)//g) not in dic:
        dic[(abs(a)//g,abs(b)//g)]=1
      else:
        dic[(abs(a)//g,abs(b)//g)]+=1
    else:
      if (-abs(a)//g,abs(b)//g) not in dic:
        dic[(-abs(a)//g,abs(b)//g)]=1
      else:
        dic[(-abs(a)//g,abs(b)//g)]=1
  else:
    if a==0 and b==0:
      cnt+=1
    elif a==0:
      if (1,0) not in dic:
        dic[(1,0)]=1
      else:
        dic[(1,0)]+=1
    elif b==0:
      if (0,1) not in dic:
        dic[(0,1)]=1
      else:
        dic[(0,1)]+=1
ans=1
s=set()
for a,b in dic.keys():
  if (a,b) in s:
    continue
  s.add((a,b))
  if a*b!=0:
    if a>0:
      if (-b,a) in dic:
        s.add((-b,a))
        cnt1=dic[(a,b)]
        cnt2=dic[(-b,a)]
        tmp=1
        for i in range(1,cnt1+1):
          tmp+=(fact[cnt1]*revfact[i]*revfact[cnt1-i])%mod
        for i in range(1,cnt2+1):
          tmp+=(fact[cnt2]*revfact[i]*revfact[cnt2-i])%mod
        ans*=tmp
        ans%=mod
      else:
        ans*=pow(2,dic[(a,b)])
        ans%=mod
    elif a<0:
      if (b,-a) in dic:
        s.add((b,-a))
        cnt1=dic[(a,b)]
        cnt2=dic[(b,-a)]
        tmp=1
        for i in range(1,cnt1+1):
          tmp+=(fact[cnt1]*revfact[i]*revfact[cnt1-i])%mod
        for i in range(1,cnt2+1):
          tmp+=(fact[cnt2]*revfact[i]*revfact[cnt2-i])%mod
        ans*=tmp
        ans%=mod
      else:
        ans*=pow(2,dic[(a,b)])
        ans%=mod
  else:
    if (b,a) in dic:
      s.add(b,a)
      cnt1=dic[(a,b)]
      cnt2=dic[(b,-a)]
      tmp=1
      for i in range(1,cnt1+1):
        tmp+=(fact[cnt1]*revfact[i]*revfact[cnt1-i])%mod
      for i in range(1,cnt2+1):
        tmp+=(fact[cnt2]*revfact[i]*revfact[cnt2-i])%mod
      ans*=tmp
      ans%=mod
    else:
      ans*=pow(2,dic[(a,b)])
      ans%=mod
print(ans+cnt-1)

Submission status: Runtime Error

Solution code:
from collections import Counter
import sys
input = sys.stdin.buffer.readline

N = int(input())

def gcd(n, m):
    if m == 0:
        return n
    return gcd(m, n % m)

def make(a, b):
    s = 1 if a * b >= 0 else -1
    a, b = abs(a), abs(b)

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

    return (a, b, s)

ABS = Counter([make(*map(int, input().split())) for _ in range(N)])

ans = 1
MOD = 10**9 + 7

for a, b, s in list(ABS.keys()):
    p = ABS[(a, b, s)]
    n = ABS[(b, a, -s)]

    ABS[(a, b, s)] = 0
    ABS[(b, a, -s)] = 0

    cnt = pow(2, p, MOD) + pow(2, n, MOD) - 1
    ans = (ans * cnt) % MOD

print((ans - 1) % MOD)