小 Dimasik 是一个有理数爱好者。他有 $n$ 个有理数 $\frac{x_i}{y_i}$。最近，Dimasik 学会了如何进行有理数减法。

回想一下，每个有理数都可以唯一地表示为最简分数 $\frac{a}{b}$，其中 $a$ 和 $b$ 是互质的整数且 $b > 0$。

我们定义函数 $d\left(\frac{x_i}{y_i}\right)$ 为有理数 $\frac{x_i}{y_i}$ 在最简分数形式下的分母。例如，$d\left(\frac{14}{6}\right) = d\left(\frac{7}{3}\right) = 3$。

现在 Dimasik 想要计算以下值：

$$\prod_{1 \le i < j \le n} d\left(\frac{x_i}{y_i} - \frac{x_j}{y_j}\right)$$

但他很快意识到这个问题对他来说太难了。Dimasik 请求你的帮助。由于该值可能非常大，请输出其对 $998\,244\,353$ 取模的结果。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 2 \cdot 10^5$)，表示 Dimasik 拥有的有理数数量。

接下来的 $n$ 行，每行包含两个整数 $x_i$ 和 $y_i$ ($0 \le x_i \le 10^9, 1 \le y_i \le 10^6$)，分别表示第 $i$ 个有理数的分子和分母。

输出格式

输出一个整数，即该问题对 $998\,244\,353$ 取模后的答案。

样例

样例输入 1

2
1 3
3 7

样例输出 1

21

样例输入 2

3
3 2
7 15
5 12

样例输出 2

7200