24182번 - 串刺し 다국어

xy 平面上に N 本の線分が配置されている．

あなたは (0,1] の一様乱数から 2 つの実数 a, b を独立に取り出す． ax+by=1 で表される直線と共有点を持つ線分の個数が，あなたのスコアとなる．

0 以上 N 以下のそれぞれのスコア i について，そのスコアが得られる確率を p_i とする．ここで p_i は有理数となることを示すことができる．p_i が既約分数 y_i/x_i で表されるとき，y_i ≡ a_i × x_i mod 1000000007 となる最小の 0 以上の整数 a_i を求めよ．与えられる入力に対し，そのような a_i が存在することが保証される．

入力は 100 個以下のデータセットからなる． 各データセットは次の形式で表される．

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

N (1 ≤ N ≤ 50) は線分の個数を表す．続く N 行にはそれぞれ線分の端点の x 座標と y 座標を表す 4 つの整数 x_i1, y_i1, x_i2, y_i2 が与えられ，i 番目の線分の端点の座標が (x_i1, y_i1) および (x_i2, y_i2) であることを表す．いずれの座標値も 1 以上 100 以下である．また，(x_i1,y_i1) ≠ (x_i2,y_i2) であることが保証される．

入力の終わりは 1 つのゼロからなる行で表される．

各データセットについて，0 以上 N 以下のそれぞれのスコアについてそのスコアが得られる確率を求め，問題文で定義された a_i を空白区切りで出力せよ．