Ordering

Time Limit : 2 sec, Memory Limit : 131072 KB

イクタ君の住む町にはN個の塔がある。 それぞれの塔には0からN−1までの異なる番号が与えられており、番号iの塔を塔iと呼ぶ。 好奇心旺盛なイクタ君はN個の塔の高さに興味を持ち、それらの大小関係を表す表Tを作ることにした。 TN × N個の要素を持ち、各要素Ti, j (0 ≤ i, j ≤ N − 1)は次のように定義される。

  • Ti, j = −1 iの高さが塔jの高さより小さい
  • Ti, j = 0 iの高さと塔jの高さが等しい
  • Ti, j = 1 iの高さが塔jの高さより大きい

イクタ君は表Tを作成するための調査として、2つの塔を選びそれらの高さを比較するということをN−1回繰り返した。

イクタ君の調査に関して以下のことがわかっている。

  • i回目の比較(1 ≤ i ≤ \ N − 1)で塔ai, 塔biが選ばれたとすると塔aiの高さが塔biの高さより大きかった。つまりTai, bi = 1, Tbi, ai = −1であった。
  • それぞれの塔は自分自身よりも大きな塔とは高々一回しか比較されていない。

残念ながらイクタ君の調査による情報だけで表Tの内容を一意に決めることができるとは限らない。 表Tがイクタ君の調査と矛盾せず、Tが定義されるような塔の高さの組み合わせが存在するときTを正しい表と呼ぶことにする。 正しい表として何通りのものが考えられるかを計算してイクタ君に教えて欲しい。

ただし、比較された2つの塔の高さは互いに異なるがすべての塔の高さが互いに異なるとは限らない。

Input

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

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

Nは塔の数を表す。 ai, bi (1 ≤ i ≤ N − 1)は塔aiが塔biより高いことを表す。

Constraints

入力中の各変数は以下の制約を満たす。

  • 1 ≤ N ≤ 200
  • 0 ≤ ai, bi < N
  • ai ≠ bi
  • 異なる塔が同じ高さであることもある。
  • イクタ君の調査結果自体が矛盾していることはなく、少なくとも1つイクタ君の調査結果と矛盾しない表Tが存在する。

Output

考えられる正しい表Tの個数の数を1,000,000,007で割ったあまりを出力せよ。

Sample Input 1

3
0 1
1 2

Output for the Sample Input 1

1

  • 正しい表Tは上図の1通りである。

Sample Input 2

3 
0 1
0 2 

Output for the Sample Input 2

3

  • 正しい表Tは上図の3通りである。

Sample Input 3

1 

Output for the Sample Input 3

1

  • 正しい表Tは上図の1通りである。

Sample Input 4

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

Output for the Sample Input 4

91

Source: ACM-ICPC Japan Alumni Group Summer Camp 2013 , Day 3, Tokyo, Japan, 2013-09-22
http://acm-icpc.aitea.net/
http://jag2013summer-day3.contest.atcoder.jp/