沙丁鱼

题目描述

钓到了 $N$ 条沙丁鱼。第 $i$ 条沙丁鱼的美味度为 $A_i$,香气浓度为 $B_i$。

从中选择 $1$ 条以上的沙丁鱼放入同一个冷藏箱,但不能同时选择互不友好的 $2$ 条沙丁鱼。

第 $i$ 条和第 $j\ (\neq i)$ 条沙丁鱼,当且仅当满足 $A_i \cdot A_j + B_i \cdot B_j = 0$ 时互不友好。

共有多少种选择沙丁鱼的方法?由于答案可能非常大,请输出除以 $1000000007$ 的余数。

输入格式

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

$N$
$A_1$ $B_1$
$:$
$A_N$ $B_N$

输出格式

输出答案除以 $1000000007$ 的余数。

样例

3
1 2
-1 1
2 -1

5

满足条件的选择方法有以下 $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

数据范围

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