22446번 - 順位付け 다국어

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

• $T_{i, j} = -1⇔ 塔iの高さが塔jの高さより小さい$

• $T_{i, j} = 0 ⇔ 塔iの高さと塔jの高さが等しい$

• $T_{i, j} = 1 ⇔ 塔iの高さが塔jの高さより大きい$

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

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

• $i$回目の比較$(1 \leq i \leq \ N - 1)$で塔$a_{i}$, 塔$b_{i}$が選ばれたとすると塔$a_{i}$の高さが塔$b_{i}$の高さより大きかった。つまり$T_{a_{i}, b_{i}} = 1$, $T_{b_{i}, a_{i}} = -1$であった。

• それぞれの塔は自分自身よりも大きな塔とは高々一回しか比較されていない。

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

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

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

$N$

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

...

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

$N$は塔の数を表す。 $a_{i}$, $b_{i}$ ($1 \leq i \leq N - 1$)は塔$a_{i}$が塔$b_{i}$より高いことを表す。

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

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

• $1 \leq N \leq 200$

• $0 \leq a_{i}, b_{i} < N$

• $a_{i} \neq b_{i}$

• 異なる塔が同じ高さであることもある。

• イクタ君の調査結果自体が矛盾していることはなく、少なくとも1つイクタ君の調査結果と矛盾しない表$T$が存在する。