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$.