お詫び（2022/07/01 22:50頃）

サンプル1の説明文1行目に誤りがありました。
「魔法3使用後」となっている箇所は、正しくは「魔法2使用後」です。当該箇所を訂正しました。

皆様にご迷惑をおかけし、大変申し訳ありません。

問題文

魔法使いのコアさんは、二次元平面上で $1, 2, \dots, N$ の番号が付いた $N$ 個の転移魔法を使用できます。

コアさんが座標 $(x, y)$ の点にいるときに転移魔法 $i$ $(1 \leq i \leq N)$ を使用すると、
座標 $(x, y)$, $( x + A_{i}, y + B_{i} )$ の $2$ 点を結ぶ線分（端点を含む）上の好きな点に転移できます。

ただし、$(A_{i}, B_{i} ) = (0, 0)$ の場合、コアさんの位置は座標 $(x, y)$ のまま変化しません。

コアさんは最初座標 $(0, 0)$ の点に立っており、これから先の転移魔法 $1, 2, \dots, N$ をこの順にすべて $1$ 回ずつ使用します。

このとき、コアさんが転移魔法 $N$ を使用した後に到達し得る格子点の座標は何種類ありますか？
答えは非常に大きくなる可能性があるので、$10^{9} + 7$ で割った余りを出力してください。

なお、「格子点」とは、二次元平面上で $x$ 座標と $y$ 座標がともに整数である点を指します。

制約

• $1 \leq N \leq 10^{5}$

• $-10^{9} \leq A_{i}, B_{i} \leq 10^{9}$ $(1 \leq i \leq N)$

• 入力はすべて整数

入力

入力は次の形式で与えられます。

$N$
$A_{1}$ $B_{1}$
$A_{2}$ $B_{2}$
   $\vdots$
$A_{N}$ $B_{N}$

• $1$ 行目には $N$ が与えられる

• $(1 + i)$ $(1 \leq i \leq N)$ 行目には $A_{i}$ と $B_{i}$ がこの順に半角スペース区切りで与えられる

出力

答えを $1$ 行に出力し、最後に改行してください。

サンプル

2
2 0
1 2

8

1
6 -8

3

4
0 0
0 0
0 0
0 0

1

10
521309021 308664469
-582348421 970764886
-963023827 -504503609
-819305054 316985726
48397449 237116403
-268699958 546643299
656066464 740195508
365802487 -484426411
-684041610 -988265057
-247873784 142659349

520304203