トーナメントの記録

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

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

入力

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

$N$
$a_1$ $b_1$
$a_2$ $b_2$
:
$a_{N-1}$ $b_{N-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$で割った余りを１行に出力する。

入出力例

入力例１

3
1 2
1 3

出力例１

2

入力例２

3
2 1
1 3

出力例２

1