配对

题号：NC276701
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

给定偶数 $n$ ，有一棵 $n$ 个点的树，点的编号是 $1,2,\dots,n$ 。你需要将这 $n$ 个点配对，形成 $\frac{n}{2}$ 对点，每个点恰好在某一对点里出现一次。

设 $d(u,v)$ 表示 $u$ 到 $v$ 的简单路径的边数，定义一种配对方案 $(u_1,v_1),(u_2,v_2),\dots,(u_{\frac{n}{2}},v_{\frac{n}{2}})$ 的权值是 $d(u_1,v_1)\times d(u_2,v_2)\times \dots \times d(u_{\frac{n}{2}},v_{\frac{n}{2}})$ 。

求所有不同的配对方案的权值之和，对 $10^9+7$ 取模。

认为两种配对方式是不同的，当且仅当存在一个点，在两种方案中与它配对的点不同。

输入描述:

第一行，一个正整数 $n$ 。

第 $2$ 至 $n$ 行，每行两个正整数 $u,v$ ，描述树上的一条边。

输出描述:

一行，一个非负整数，表示答案。

示例1

输入

复制

输出

复制

说明

点  与  中的某个点配对，剩下的两个点配对，有三种配对方案，每种方案的权值都是 ，所以权值之和为 。

示例2

输入

复制

输出

复制

示例3

输入

复制

输出

复制

备注:

；
。