配点 : $900$ 点

問題文

$N$ を偶数とします。

$N$ 頂点の木があります。 頂点には $1, 2, ..., N$ と番号が振られています。 各 $i$ ($1 \leq i \leq N - 1$) について、$i$ 番目の辺は頂点 $x_i$ と $y_i$ を結んでいます。

すぬけ君は、次のようにして木をリボンで飾りつけようと思っています。

まず、$N$ 個の頂点を $N / 2$ 組のペアに分けます。 このとき、各頂点はちょうど $1$ つのペアに属さなければなりません。 次に、各ペア $(u, v)$ について、$1$ 本のリボンを $u$-$v$ 間の最短パスに含まれるすべての辺を通るように張ります。

すぬけ君はペアの分け方を工夫し、「どの辺にも少なくとも $1$ 本のリボンが張られている」という条件が成り立つようにしようとしています。 条件が成り立つようなペアの分け方は何通りでしょうか？ $10^9 + 7$ で割った余りを求めてください。 ただし、$2$ 通りのペアの分け方が異なるとは、あるペアが一方には含まれるが他方には含まれないことを言います。

制約

• $N$ は偶数である。
• $2 \leq N \leq 5000$
• $1 \leq x_i, y_i \leq N$
• 与えられるグラフは木である。

入力

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

$N$

$x_1$ $y_1$

$x_2$ $y_2$

$:$

$x_{N - 1}$ $y_{N - 1}$

出力

条件が成り立つようなペアの分け方は何通りか？ $10^9 + 7$ で割った余りを出力せよ。

4
1 2
2 3
3 4

2

ペアの分け方は次図の $3$ 通りであり、右側の $2$ 通りが条件を満たします。

4
1 2
1 3
1 4

3

ペアの分け方は次図の $3$ 通りであり、すべて条件を満たします。

6
1 2
1 3
3 4
1 5
5 6

10

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

672