题目描述

设 $N$ 为偶数。

有一棵 $N$ 个顶点的树。顶点编号为 $1, 2, \ldots, N$。对于每个 $i$（$1 \leq i \leq N-1$），第 $i$ 条边连接顶点 $x_i$ 和 $y_i$。

すぬけ君打算用丝带按照如下方式装饰这棵树。

首先，将 $N$ 个顶点分成 $N/2$ 对，每个顶点恰好属于一对。接着，对于每一对 $(u, v)$，用一根丝带沿着 $u$ 到 $v$ 的最短路径，将路径上的所有边都覆盖。

すぬけ君希望通过巧妙地分组，使得“每一条边都至少被一根丝带覆盖”。请问有多少种分组方式满足条件？请输出对 $10^9+7$ 取模的结果。
如果两种分组方式中，存在某一对只属于其中一种方式，则认为这两种分组方式不同。

输入格式

输入以如下格式从标准输入读入：

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

输出格式

输出满足条件的分组方式数，对 $10^9+7$ 取模。

样例 1

输入

4
1 2
2 3
3 4

输出

2

样例 2

输入

4
1 2
1 3
1 4

输出

3

样例 3

输入

6
1 2
1 3
3 4
1 5
5 6

输出

10

样例 4

输入

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

输出

672

说明/提示

限制条件

• $N$ 是偶数。
• $2 \leq N \leq 5000$
• $1 \leq x_i, y_i \leq N$
• 给定的图是一棵树。

样例解释 1

分组方式有如下图的 $3$ 种，其中右侧的 $2$ 种满足条件。

样例解释 2

分组方式有如下图的 $3$ 种，全部都满足条件。

由 ChatGPT 4.1 翻译