串刺し

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

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

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

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

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

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

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

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