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 翻译