시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초 512 MB111100.000%

문제

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

예제 입력 1

2
1 3
3 7

예제 출력 1

21

예제 입력 2

3
3 2
7 15
5 12

예제 출력 2

7200