该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

背景

在密码学中，常常需要处理多重模运算来确保信息的安全传输。一个典型的应用是为了分解一个秘密值，使得每一个分解的值都不会泄露任何关于秘密值的有效信息。然而，在某些情况下，我们需要从这些分解的值中恢复原始的秘密值。

题目描述

假设你是一名密码学家，正在处理一个秘密值的多重模运算。你已经将秘密值分解成了若干个模数下的余数。现在，你需要通过这些余数恢复原始的秘密值。具体来说，给定一组方程：

$$\begin{cases} x \equiv a_1 \pmod{n_1} \\ x \equiv a_2 \pmod{n_2} \\ \vdots \\ x \equiv a_k \pmod{n_k} \end{cases}$$

其中 $a_i$ 和 $n_i$ 是已知的正整数，并且 $n_i$互质。你的任务是求解这个方程组，找出所有满足条件的最小非负整数$x$。

输入

• 第一行包含一个整数 $k$，表示方程的数量。
• 接下来 $k$ 行，每行包含两个正整数 $a_i$ 和 $n_i$ ，分别表示一个方程中的余数和模数。保证所有 $n_i$ 互质。

输出

输出一个整数$x$，即满足所有方程的最小非负整数解。结果可能会很大,答案对 $10^{11}+7$取余

样例输入

3
2 3
3 5
2 7

样例输出

23

提示

样例中的方程组为：

$$\begin{cases} x \equiv 2 \pmod{3} \\ x \equiv 3 \pmod{5} \\ x \equiv 2 \pmod{7} \end{cases}$$

可以求解得到最小的非负整数解为23。

数据范围及约定

对于33%的数据,$2 ≤ k ≤ 100$,$2 ≤ a_i < n_i ≤ 10^6$

$$\\$$

对于33%的数据,$2 ≤ k ≤ 500$,$2 ≤ a_i < n_i ≤ 10^8$

$$\\$$

对于34%的数据,$2 ≤ k ≤ 1000$,$2 ≤ a_i < n_i ≤10^{10}$