E - ∙ (子弹)

得分：$500$ 点

题目描述

我们捕获了 $N$ 条沙丁鱼。第 $i$ 条沙丁鱼的“美味”和“香气”分别为 $A_i$ 和 $B_i$。

我们将选择一条或多条沙丁鱼放入冷却器中。然而，两条不和谐的沙丁鱼不能同时选择。

第 $i$ 条和第 $j$ 条沙丁鱼 $(i \neq j)$ 是不和谐的当且仅当 $A_i \cdot A_j + B_i \cdot B_j = 0$。

有多少种方式可以选择放入冷却器中的沙丁鱼集合？由于计数可能非常大，所以对 $1000000007$ 取模后输出。

约束

• 输入中的所有值都是整数。
• $1 \leq N \leq 2 \times 10^5$
• $-10^{18} \leq A_i, B_i \leq 10^{18}$

输入

从标准输入中按以下格式给出输入：

$N$

$A_1$ $B_1$

$:$

$A_N$ $B_N$

输出

按 $1000000007$ 取模后输出。

3
1 2
-1 1
2 -1

5

以下是五种选择沙丁鱼集合的方式：

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

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

479