Submission #13341859


Source Code Expand

Copy
import sys
from collections import defaultdict
from math import gcd

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 10**9 + 7

N = int(readline())
m = map(int, read().split())
A, B = zip(*zip(m, m))

pow2 = [1] * (N + 10)
for n in range(1, N + 10):
    pow2[n] = pow2[n - 1] * 2 % MOD

def to_standard_form(a, b):
    if a == 0:
        return (0, 1)
    g = gcd(a, b)
    a //= g
    b //= g
    if a < 0:
        return (-a, -b)
    return (a, b)

counter0 = defaultdict(int)
counter1 = defaultdict(int)
origin = 0
for a, b in zip(A, B):
    if a == b == 0:
        origin += 1
        continue
    a, b = to_standard_form(a, b)
    if b <= 0:
        counter0[(a, b)] += 1
    else:
        counter1[(b, -a)] += 1
        counter0[(b, -a)] += 0

answer = origin
k = 1
for key, cnt0 in counter0.items():
    cnt1 = counter1[key]
    x = pow2[cnt0] + pow2[cnt1]
    k = k * (x - 1) % MOD

answer += k - 1
answer %= MOD
print(answer)

Submission Info

Submission Time
Task E - ∙ (Bullet)
User maspy
Language Python (3.8.2)
Score 500
Code Size 1049 Byte
Status
Exec Time 765 ms
Memory 96064 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt
Subtask1 500 / 500 sample_01.txt, sample_02.txt, sub1_01.txt, sub1_02.txt, sub1_03.txt, sub1_04.txt, sub1_05.txt, sub1_06.txt, sub1_07.txt, sub1_08.txt, sub1_09.txt, sub1_10.txt, sub1_11.txt, sub1_12.txt, sub1_13.txt, sub1_14.txt, sub1_15.txt, sub1_16.txt, sub1_17.txt, sub1_18.txt, sub1_19.txt, sub1_20.txt, sub1_21.txt
Case Name Status Exec Time Memory
sample_01.txt 21 ms 9240 KB
sample_02.txt 22 ms 9288 KB
sub1_01.txt 765 ms 96064 KB
sub1_02.txt 21 ms 9352 KB
sub1_03.txt 25 ms 9400 KB
sub1_04.txt 19 ms 9244 KB
sub1_05.txt 19 ms 9352 KB
sub1_06.txt 21 ms 9536 KB
sub1_07.txt 19 ms 9400 KB
sub1_08.txt 21 ms 9468 KB
sub1_09.txt 18 ms 9400 KB
sub1_10.txt 22 ms 9348 KB
sub1_11.txt 166 ms 27564 KB
sub1_12.txt 357 ms 48368 KB
sub1_13.txt 516 ms 63848 KB
sub1_14.txt 377 ms 49304 KB
sub1_15.txt 95 ms 18900 KB
sub1_16.txt 321 ms 44596 KB
sub1_17.txt 226 ms 36880 KB
sub1_18.txt 409 ms 62064 KB
sub1_19.txt 111 ms 22236 KB
sub1_20.txt 331 ms 52760 KB
sub1_21.txt 217 ms 37684 KB