∙ (Bullet)

题目描述

我们捕获了 $N$ 条沙丁鱼。第 $i$ 条沙丁鱼的 美味度 和 香气度 分别为 $A_i$ 和 $B_i$。 我们将从这些沙丁鱼中选择一个或多个放入保温箱。但关系不和睦的两条沙丁鱼不能同时被选择。 当且仅当 $A_i \cdot A_j + B_i \cdot B_j = 0$ 时，第 $i$ 条和第 $j$ 条沙丁鱼 $(i \neq j)$ 关系不和睦。 有多少种方法可以选择放入保温箱的沙丁鱼集合？由于计数可能非常大，请对 $1000000007$ 取模后输出结果。

输入格式

标准输入（Standard Input）的输入格式如下： $N$ $A_1$ $B_1$ : $A_N$ $B_N$

输出格式

输出对 $1000000007$ 取模的计数结果。

3
1 2
-1 1
2 -1

5

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

479

提示

输入中的所有数值均为整数。 $1 \leq N \leq 2 \times 10^5$ $-10^{18} \leq A_i, B_i \leq 10^{18}$共有五种选择沙丁鱼集合的方法，如下：

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

标签: AtCoder|abc168E

来源

AtCoder|abc168E