← 返回题目列表

AtCoder · abc168_e

E. ∙(项目符号)

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

我们已经抓住了 N 沙丁鱼。的 美味 和 香味 的 i-第沙丁鱼是 分别是 A_i 和 B_i。

我们将选择一条或多条这些沙丁鱼并将它们放入冷却器中。然而,两条关系不睦的沙丁鱼不能同时选择。

的 i-th 和 j-th 沙丁鱼 (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.


示例输入 1

3
1 2
-1 1
2 -1

示例输出 1

5

沙丁鱼套餐有五种选择方式,如下:

  • 的 1-st
  • 的 1-st 和 2-nd
  • 的 2-nd
  • 的 2-nd 和 3-rd
  • 的 3-rd

示例输入 2

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

示例输出 2

479