カフェオレ

問題

$N$ 個のカフェオレがあります。

$i$ 番目のカフェオレは、コーヒー $c_i$ グラムとミルク $m_i$ グラムが混ざった $c_i + m_i$ グラムのカフェオレです。

これらを混ぜ合わせることで、コーヒー $x$ グラムとミルク $y$ グラムが混ざった $x + y$ グラムのカフェオレを作ることを考えます。

具体的には、 $i$ 番目のカフェオレを $p_i$ ($0 \leq p_i \leq 1$) の割合だけ使用した場合、

• $\displaystyle \sum_{i=1}^N p_i c_i = x$
• $\displaystyle \sum_{i=1}^N p_i m_i = y$

として、コーヒーが $x$ グラム、ミルクが $y$ グラムのカフェオレが作られます。

このようなカフェオレを作れる $1$ 以上の整数の組 $(x, y)$ の個数を $10^9 + 7$ で割った余りを出力してください。

制約

• $1 \leq N \leq 10^5$
• $1 \leq c_i, m_i \leq 10^9$ ($1 \leq i \leq N$)

入力

$N$
$c_1$ $m_1$
$\vdots$
$c_N$ $m_N$

出力

作れるカフェオレのうち、コーヒーの量とミルクの量が $1$ 以上の整数となるようなものの個数を $10^9 + 7$ で割った余りを $1$ 行で出力してください。

入力例 1

2
1 1
1 3

出力例 1

4

あり得るコーヒーの量 $x$ とミルクの量 $y$ の組み合わせ $(x, y)$ を全て列挙すると、下記のようになります。

$(x, y) = (1, 1), (1, 2), (1, 3), (2, 4)$

入力例 2

3
1 1
1 3
3 1

出力例 2

15

入力例 3

3
1 1
2 2
3 3

出力例 3

6

---