時間制限 : sec, メモリ制限 : KB
English / Japanese  

Problem E: Huge Family

Dango氏の家は想像を絶する大家族である。昔はおよそ100人の家族だったのだが、今では一つの街を作れるほど巨大になり、もうすぐこの星を埋め尽くすのではないか、なんていう冗談も囁かれている。彼らは皆穏やかで優しい性格をしていて、家族全員仲良しである。

彼らは全員携帯電話を使って連絡を取り合っている。もちろん、全員揃って家族割引に加入している。この家族割引は以下のようなものである。a 氏が b 氏を、b 氏が a 氏を相手に指定すると、その2人の間では家族割引が適用でき、その通話の単位時間あたりの料金が普通より安い f(a, b) 円になる。それぞれの人は最大2回まで家族割引を同時に適用することができるが、同じ2人組が2回適用することは許されない。そして今、適切に相手を選んだので、Dango一家の全員が家族割引を2回適用している。

なにしろ人数が多いので、家族全員に電話を使って連絡をすることはとても大変である。Dango氏は、家族割引を使って clan という連絡網を作ることを考えた。clan の定義を以下に示そう。

clan とは、家族割引の適用された通話の部分集合 S のうち、以下のようなものである。

  1. どんな2人 (仮に i 氏、j 氏とする) に対しても、i 氏から家族割引が適用された通話のみを経由して (直接、あるいは間接的に) j 氏に連絡を取ることができるならば、i 氏から S に含まれる通話のみを経由して (直接、あるいは間接的に) j 氏に連絡をとることができる。
  2. 条件 1 を満たした上で、S に含まれる通話の単位時間あたりの料金の和が最小になる。

clan を使うことで、より効率的に連絡が行えるようになる。例えば、ある人が、clan に含まれる (彼と関係した) 全ての通話で連絡事項を送ったとする。なおかつ、clanの全ての人が「clan に含まれる通話で連絡が着たならば、他の全ての clan に含まれる通話でその連絡を伝える」というルールに従ったとする。このとき、値引きされた通話のみを経由して連絡を取れる全ての人に必ずその連絡が行き渡ることと、その連絡が同じ人のところに2回以上回ってこないことが証明できる。

さて、あなたにはDango一家の家族割引の適用状況に関する情報が与えられる。何通りの異なる clan を作ることができるか計算するプログラムを作成してほしい。答えは非常に大きくなりうるので、 mod 10007 で出力せよ。

Input

入力は複数のテストケースから構成される。

各テストケースの最初の行には、家族の人数 nが与えられる。続く n 行のうち i 行目には i 番目の人に関する情報が与えられ、各行は4つの整数を含む。 最初の2つの数はそれぞれ、家族割引の相手 b[0] と、その相手に対する単位時間あたりの通話料 f(i, b[0]) を表す。 続く2つの数も同様に、b[1] と f(i, b[1]) を表す。

n = 0 のとき入力の終わりを示す。

Output

clan の数を mod 10007 で出力せよ。

Constraints

  • 3 ≤ n ≤ 100,000

Sample Input

3
1 1 2 3
0 1 2 2
1 2 0 3
7
1 2 2 1
0 2 3 2
0 1 3 1
2 1 1 2
5 3 6 2
4 3 6 1
4 2 5 1
0

Output for the Sample Input

1
2