N - 木 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

Problem Statement

頂点 1 から頂点 N までが紙が描かれている。すぬけ君は、頂点 a_i と頂点 b_i の間に辺を描き、木にすることにした。木を書いている途中で常に辺が連結になっているようにしたいとき、辺を描く順番は何通り考えられるか、mod 1,000,000,007 で求めよ。

Constraints

  • 2 ≤ N ≤ 1000
  • 1 ≤ a_i, b_i ≤ N
  • The input will represent a tree.

Input Format

入力は以下の形式で標準入力から与えられる。
N
a_1 b_1
...
a_{N-1} b_{N-1}

Output Format

答えを一行に出力せよ。

Sample Input 1

4
1 2
2 3
3 4

Sample Output 1

4
  • 1-2 -> 2-3 -> 3-4
  • 2-3 -> 1-2 -> 3-4
  • 2-3 -> 3-4 -> 1-2
  • 3-4 -> 2-3 -> 1-2
の 4 通りの順番が考えられる。(1-2 と 3-4 の辺を先に書いてしまうと、その時点で辺が非連結となってしまう。)

Sample Input 2

8
1 2
4 6
6 7
3 2
2 4
4 5
8 6

Sample Output 2

752