201012: [AtCoder]ARC101 E - Ribbons on Tree

Problem Statement

Let $N$ be an even number.

There is a tree with $N$ vertices. The vertices are numbered $1, 2, ..., N$. For each $i$ ($1 \leq i \leq N - 1$), the $i$-th edge connects Vertex $x_i$ and $y_i$.

Snuke would like to decorate the tree with ribbons, as follows.

First, he will divide the $N$ vertices into $N / 2$ pairs. Here, each vertex must belong to exactly one pair. Then, for each pair $(u, v)$, put a ribbon through all the edges contained in the shortest path between $u$ and $v$.

Snuke is trying to divide the vertices into pairs so that the following condition is satisfied: "for every edge, there is at least one ribbon going through it." How many ways are there to divide the vertices into pairs, satisfying this condition? Find the count modulo $10^9 + 7$. Here, two ways to divide the vertices into pairs are considered different when there is a pair that is contained in one of the two ways but not in the other.

Constraints

• $N$ is an even number.
• $2 \leq N \leq 5000$
• $1 \leq x_i, y_i \leq N$
• The given graph is a tree.

Input

Input is given from Standard Input in the following format:

$N$
$x_1$ $y_1$
$x_2$ $y_2$
$:$
$x_{N - 1}$ $y_{N - 1}$

Output

Print the number of the ways to divide the vertices into pairs, satisfying the condition, modulo $10^9 + 7$.

Sample Input 1

4
1 2
2 3
3 4

Sample Output 1

2

There are three possible ways to divide the vertices into pairs, as shown below, and two satisfy the condition: the middle one and the right one.

Sample Input 2

4
1 2
1 3
1 4

Sample Output 2

3

There are three possible ways to divide the vertices into pairs, as shown below, and all of them satisfy the condition.

Sample Input 3

6
1 2
1 3
3 4
1 5
5 6

Sample Output 3

10

Sample Input 4

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

Sample Output 4

672