题目描述

给定一个大小为 $n$ 的树，保证 $n$ 为偶数且小于 $5000$

您需要给树上的点两两配对，对于一组对子 $(u,v)$，在树上将 $u\to v$ 的路径染色，定义一个配对方案合法当且仅当所有边都有颜色。

求方案数对 $10^9+7$ 取模。

说明/提示

$\begin{array}{l}2\le N\le 5000\\2\mid N\\\text{保证输入的一定是一棵树}\end{array}$

样例1解释

样例2解释

合法的$3$种情况如下：

样例 #1

样例输入 #1

4
1 2
2 3
3 4

样例输出 #1

2

样例 #2

样例输入 #2

4
1 2
1 3
1 4

样例输出 #2

3

样例 #3

样例输入 #3

6
1 2
1 3
3 4
1 5
5 6

样例输出 #3

10

样例 #4

样例输入 #4

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

样例输出 #4

672

提示

制約

• $N$ は偶数である。
• $2\ \leq\ N\ \leq\ 5000$
• $1\ \leq\ x_i,\ y_i\ \leq\ N$