题目描述

设$N$为偶数。

有一个包含$N$个顶点的树，顶点按$1, 2, ..., N$进行编号。对于每个$i$（$1 \leq i \leq N - 1$），第$i$条边连接顶点$x_i$和$y_i$。

Snuke想要用丝带来装饰这棵树。

首先，他将$N$个顶点划分为$N/2$对。每个顶点必须属于且仅属于一对。然后，对于每对$(u, v)$，通过连接$u$和$v$之间最短路径上的所有边，穿过一条丝带。

Snuke试图将顶点划分为成对的顶点，使得满足以下条件：“对于每条边，至少有一条丝带穿过它。”有多少种划分顶点的方式可以满足这个条件？计算模$10^9 + 7$下的数量。这里，当两种划分顶点的方式中存在一对顶点在一种方式中出现而在另一种方式中不存在时，认为这两种方式是不同的。

约束条件

• $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$取模。

---

示例输入 1

4
1 2
2 3
3 4

示例输出 1

2

有三种划分顶点的方式，如下图所示，其中有两种满足条件：中间和右边的两种。

---

示例输入 2

4
1 2
1 3
1 4

示例输出 2

3

有三种划分顶点的方式，如下图所示，其中所有方式都满足条件。

---

示例输入 3

6
1 2
1 3
3 4
1 5
5 6

示例输出 3

10

---

示例输入 4

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

示例输出 4

672