分数: 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