Ranking

Time limit2sMemory limit512 MB

Summary

Given N-1 comparisons where tower a is taller than b, and each tower loses to a taller tower at most once, count the possible total order tables consistent with these facts.

Level: Medium7 of 10
Topics: Combinatorics, Tree, Dynamic programming, Graph
Solved: No attempts yet

Problem

In the town where Ikuta lives there are $N$ towers. Each tower is given a distinct number from 0 to $N-1$ , and the tower numbered $i$ is called tower $i$ . Curious Ikuta took an interest in the heights of the $N$ towers and decided to build a table $T$ that describes their order. $T$ has $N \times N$ elements, and each element $T_{i, j} (0 \leq i, j \leq N - 1)$ is defined as follows.

$T_{i, j} = -1 \iff$ the height of tower $i$ is less than the height of tower $j$
$T_{i, j} = 0 \iff$ the height of tower $i$ equals the height of tower $j$
$T_{i, j} = 1 \iff$ the height of tower $i$ is greater than the height of tower $j$

To build the table $T$ , Ikuta repeatedly chose two towers and compared their heights, $N-1$ times in total.

The following is known about Ikuta's survey.

If tower $a_{i}$ and tower $b_{i}$ were chosen in the $i$ -th comparison $(1 \leq i \leq N - 1)$ , then the height of tower $a_{i}$ was greater than the height of tower $b_{i}$ . That is, $T_{a_{i}, b_{i}} = 1$ and $T_{b_{i}, a_{i}} = -1$ .
Each tower was compared with a taller tower at most once.

Unfortunately, the information from Ikuta's survey alone does not always determine the contents of table $T$ uniquely. When $T$ does not contradict Ikuta's survey and there exists a combination of tower heights for which $T$ is defined, call $T$ a correct table. Compute how many correct tables are possible and tell Ikuta.

Note that the two compared towers have different heights, but not all tower heights are necessarily different.

Input

The input is given in the following format.

$N$

$a_{1}$ $b_{1}$

...

$a_{N-1}$ $b_{N-1}$

$N$ represents the number of towers. $a_{i}$ , $b_{i}$ ( $1 \leq i \leq N - 1$ ) mean that tower $a_{i}$ is taller than tower $b_{i}$ .

Output

Output the number of possible correct tables $T$ modulo 1,000,000,007.

Constraints

Each variable in the input satisfies the following conditions.

$1 \leq N \leq 200$
$0 \leq a_{i}, b_{i} < N$
$a_{i} \neq b_{i}$
Different towers may have the same height.
Ikuta's survey results themselves are consistent, and at least one table $T$ exists that does not contradict the survey results.

Examples4

Example 1
Input
```
3
0 1
1 2
```
Expected output
```
1
```
Example 2
Input
```
3
0 1
0 2
```
Expected output
```
3
```
Example 3
Input
```
1
```
Expected output
```
1
```
Example 4
Input
```
7
0 1
1 2
2 3
3 4
0 5
0 6
```
Expected output
```
91
```