配点: $500$ 点

問題文

$N$ 匹のイワシが釣れました。$i$ 匹目のイワシの美味しさは $A_i$、香り高さは $B_i$ です。

この中から $1$ 匹以上のイワシを選んで同じクーラーボックスに入れますが、互いに仲が悪い $2$ 匹を同時に選ぶことはできません。

$i$ 匹目と $j (\neq i)$ 匹目のイワシは、$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

条件を満たす選び方は以下の $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