AT_abc168_e [ABC168E] ∙ (Bullet)

题目描述

有 $N$ 条沙丁鱼被钓上来了。第 $i$ 条沙丁鱼的美味度为 $A_i$，香气度为 $B_i$。

现在要从中选择至少 $1$ 条沙丁鱼放入同一个冷藏箱，但不能同时选择两条互相不和的沙丁鱼。

当且仅当第 $i$ 条和第 $j$ 条沙丁鱼满足 $A_i \cdot A_j + B_i \cdot B_j = 0$ 且 $i \neq j$ 时，这两条沙丁鱼互相不和。

请问有多少种选择沙丁鱼的方法？由于答案可能非常大，请输出对 $1000000007$ 取模的结果。

输入格式

输入以如下格式从标准输入给出。

$N$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_N$ $B_N$

输出格式

输出对 $1000000007$ 取模的答案。

输入输出样例 #1

输入 #1

3
1 2
-1 1
2 -1

输出 #1

5

输入输出样例 #2

输入 #2

10
3 2
3 2
-1 1
2 -1
-3 -9
-8 12
7 7
8 1
8 2
8 4

输出 #2

479

说明/提示

限制条件

• 输入均为整数。
• $1 \leq N \leq 2 \times 10^5$
• $-10^{18} \leq A_i, B_i \leq 10^{18}$

样例解释 1

满足条件的选法共有 $5$ 种：

• 只选第 $1$ 条
• 选第 $1$ 条和第 $2$ 条
• 只选第 $2$ 条
• 选第 $2$ 条和第 $3$ 条
• 只选第 $3$ 条

由 ChatGPT 4.1 翻译