010 - トーナメントの記録

時間制限 1 秒 / メモリ制限 256 MB / 得点 12 / x 0 /


TLE
1sec
MLE
256MB
得点
12

問題文

$N$人が参加するトーナメントを行いました。トーナメントでは一対一で対戦を行い、勝ち負けを決定します。勝った方が次の試合に進んでゆき、最終的に残った一人が優勝します。トーナメントが行われる会場はひとつしかないので、同時に行えるのは1試合のみです。

トーナメントが終わって優勝者が決まるまで、記録係のあなたは対戦の勝者と敗者を記録しました。あなたは対戦ごとに1枚の紙を使って正しく記録しましたが、記録した紙の順序がいくつか入れ替わった可能性があります。

順序が入れ替わった可能性のある対戦の記録から、あり得る対戦の順番が何通りあるかを求めるプログラムを作成せよ。ただし、トーナメントの参加者には1から$N$までの番号が割り当てられているものとする。

入力

入力は以下の形式で与えられる。

$N$
$a_1$ $b_1$
$a_2$ $b_2$
:
$a_{N-1}$ $b_{N-1}$

1行目に出場者の数$N$ ($2 \leq N \leq 1000$)が与えられる。続く$N-1$行に、試合の勝者と敗者の記録$a_i$,$b_i$ ($1 \leq a_i,b_i \leq N$)が与えられる。ただし、$a_i$が勝者、$b_i$が敗者を表す。

出力

あり得る対戦の順番が何通りあるかを表す数を$10^6$で割った余りを1行に出力する。

入出力例

入力例1

3
1 2
1 3

出力例1

2

入力例2

3
2 1
1 3

出力例2

1