Ordering

There are N towers in the town where Ikta lives. Each tower is given a different number from 0 to N-1, and the tower with number i is called tower i. Curious Ikta was interested in the height of the N towers and decided to make a table T showing the magnitude relationship between them. T has N × N elements, and each element Ti, j (0 ≤ i, j ≤ N − 1) is defined as follows.

• Ti, j = −1 ⇔ The height of tower i is smaller than the height of tower j
• Ti, j = 0 ⇔ The height of tower i is equal to the height of tower j
• Ti, j = 1 ⇔ The height of tower i is larger than the height of tower j

As a survey to create Table T, Ikta repeated N-1 times to select two towers and compare their heights.

We know the following about Ikta's investigation.

• If tower ai and tower bi were selected in the i-th comparison (1 ≤ i ≤ \ N − 1), the height of tower ai was larger than the height of tower bi. That is, Tai, bi = 1, Tbi, ai = −1.
• Each tower has been compared to a tower larger than itself at most once.

Unfortunately, it is not always possible to uniquely determine the contents of Table T based on the information obtained from Ikta's research. If the table T is consistent with Ikta's research and there is a combination of tower heights in which T is defined, we will call T the correct table. Please calculate how many kinds of correct tables you can think of and tell Ikta.

However, although the heights of the two towers compared are different from each other, not all towers are different from each other.

Input

The input is given in the following format.

N a1 b1 ... aN−1 bN−1

N represents the number of towers. ai, bi (1 ≤ i ≤ N − 1) indicates that the tower ai is higher than the tower bi.

Constraints

Each variable being input satisfies the following constraints.

• 1 ≤ N ≤ 200
• 0 ≤ ai, bi <N
• ai ≠ bi
• Different towers may be the same height.
• Ikta's findings are not inconsistent, and there is at least one Table T that is consistent with Ikta's findings.

Output

Output the remainder of dividing the number of possible correct number of tables T by 1,000,000,007.

Examples

Input

3 0 1 1 2

Output

1

Input

3 0 1 0 2

Output

3

Input

1

Output

1

Input

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

Output

91

inputFormat

Input

The input is given in the following format.

N a1 b1 ... aN−1 bN−1

N represents the number of towers. ai, bi (1 ≤ i ≤ N − 1) indicates that the tower ai is higher than the tower bi.

Constraints

Each variable being input satisfies the following constraints.

• 1 ≤ N ≤ 200
• 0 ≤ ai, bi <N
• ai ≠ bi
• Different towers may be the same height.
• Ikta's findings are not inconsistent, and there is at least one Table T that is consistent with Ikta's findings.

outputFormat

Output

Output the remainder of dividing the number of possible correct number of tables T by 1,000,000,007.

Examples

Input

3 0 1 1 2

Output

1

Input

3 0 1 0 2

Output

3

Input

1

Output

1

Input

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

Output

91

样例

1

1