AT_arc101_c.[ARC101E] Ribbons on Tree

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

限制条件

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

样例解释 1

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

样例解释 2

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

由 ChatGPT 4.1 翻译