꼬치 꿰기

xy 평면에 $N$개의 선분이 놓여 있다.

$(0,1]$ 구간의 균등 난수에서 실수 $a$, $b$를 서로 독립으로 뽑는다. $ax+by=1$로 나타나는 직선과 공통점을 갖는 선분의 개수가 점수가 된다.

$0$ 이상 $N$ 이하의 각 점수 $i$에 대해, 그 점수를 얻을 확률을 $p_i$라 하자. $p_i$는 유리수이다. $p_i$를 기약분수 $y_i/x_i$로 나타냈을 때, $y_i \equiv a_i \times x_i \pmod{1000000007}$을 만족하는 가장 작은 $0$ 이상의 정수 $a_i$를 구하라. 주어진 입력에 대해 그런 $a_i$가 존재함이 보장된다.

입력은 최대 100개의 데이터셋으로 이루어진다. 각 데이터셋은 다음 형식으로 주어진다.

N
x11 y11 x12 y12
...
xN1 yN1 xN2 yN2

$N$ ($1 \le N \le 50$)은 선분의 개수이다. 이어지는 $N$개의 줄에는 각각 $i$번째 선분의 두 끝점 $(x_{i1}, y_{i1})$, $(x_{i2}, y_{i2})$를 나타내는 정수 네 개 $x_{i1}, y_{i1}, x_{i2}, y_{i2}$가 주어진다. 모든 좌표값은 1 이상 100 이하이다. 각 선분의 두 끝점은 서로 다르다. 입력의 끝은 0 한 개로 이루어진 줄이다.

각 데이터셋에 대해 $0$ 이상 $N$ 이하의 각 점수가 나올 확률을 구하고, 문제에서 정의한 $a_i$를 공백으로 구분하여 한 줄에 출력하라.