Apology (around 22:50, 2022/07/01)

There was an error in the first line of the explanation for Sample 1.
The part that said "after using Magic 3" should correctly read "after using Magic 2". This part has been corrected.

We deeply apologize for any inconvenience caused.

Problem Statement

The wizard Koa can use $N$ teleportation spells numbered $1, 2, \dots, N$ on a two-dimensional plane.

When Koa is at the point with coordinates $(x, y)$ and uses teleportation spell $i$ $(1 \leq i \leq N)$,
she can teleport to any point on the line segment (including its endpoints) connecting the $2$ points with coordinates $(x, y)$ and $( x + A_{i}, y + B_{i} )$.

However, if $(A_{i}, B_{i} ) = (0, 0)$, Koa's position remains at coordinates $(x, y)$ and does not change.

Koa initially stands at the point with coordinates $(0, 0)$, and from now on she will use all of the teleportation spells $1, 2, \dots, N$ exactly $1$ time each, in this order.

How many different coordinates of lattice points can Koa reach after using teleportation spell $N$?
Since the answer can be very large, output it modulo $10^{9} + 7$.

Here, a "lattice point" is a point on the two-dimensional plane whose $x$ and $y$ coordinates are both integers.

Constraints

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

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

• All inputs are integers

Input

The input is given in the following format.

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

• The $1$st line contains $N$

• The $(1 + i)$-th $(1 \leq i \leq N)$ line contains $A_{i}$ and $B_{i}$ in this order, separated by a single-byte space

Output

Output the answer on $1$ line, followed by a newline.

Sample

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