23168번 - Rational Dimasik 다국어

문제

Little Dimasik is a rational numbers fan. He has $n$ rational numbers $\frac{x_i}{y_i}$. Recently Dimasik learned how to subtract rational numbers.

Recall that every rational number may be expressed in a unique way as an irreducible fraction $\frac{a}{b},ドル where $a$ and $b$ are coprime integers and $b > 0$.

Let us define the function $d \left( \frac{x_i}{y_i} \right)$ as the denominator of the rational number $\frac{x_i}{y_i}$ in irreducible notation. For example, $d(\frac{14}{6}) = d(\frac{7}{3}) = 3$.

Now Dimasik wants to calculate the value $$\prod\limits_{1 \le i < j \le n} d \left( \left| \frac{x_i}{y_i} - \frac{x_j}{y_j} \right| \right)\text{.}$$ But soon he realized that this problem is too hard for him. Dimasik asks you to help him. As the value may be very large, find it modulo 998ドル,244円,353円$.

입력

The first line contains one integer $n$ (1ドル \le n \le 2 \cdot 10^5$) denoting the number of rational numbers Dimasik has.

Each of the following $n$ lines contains two integers $x_i$ and $y_i$ (0ドル \le x_i \le 10^{9},ドル 1ドル \le y_i \le 10^6$) representing the numerator and denominator of the $i$-th rational number.

출력

Print a single integer --- the answer to the problem modulo 998ドル,244円,353円$.

제한

힌트