Tournament Record

　

　We had a tournament in which $N$ people participated. In the tournament, the participants play against each other one-on-one to decide who wins and who loses. The winner moves on to the next match, and the one who remains in the end is the winner. Since there is only one venue for the tournament, only one match can be played at a time.

As the recorder, you recorded the winners and losers of each match until the tournament was over and the winner was determined. You recorded correctly, using a sheet of paper for each match, but some of the papers you recorded may be rearranged by ascident.

Write a program to find out how many possible orders of the games are possible from the records of the games where the order may have been switched. Assume that the participants in the tournament are assigned numbers from 1 to $N$.

Input

The input is given in the following order.

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

The first line gives the number of contestants $N$ ($2 \leq N \leq 1000$). In the following $N-1$ lines, the records of the winners and losers of the match $a_i$, $b_i$ ($1 \leq a_i,b_i \leq N$) are given. $a_i$ represents the winner and $b_i$ represents the loser.

Output

Output the remainder of the number of possible orders of the matches divided by $10^6$ in a line.

Sample Input and Output

Sample Input 1

3
1 2
1 3

Sample Output 1

2

Sample Input 2

3
2 1
1 3

Sample Output 2

1

---