作为C市的中考状元，小针毫无悬念地进入了面子中学学习信息学竞赛。

在进入面子中学后，他在王学长的指引下学习了许多算法，其中一个就是点分治。

小针学的点分治是王学长教给他的，它是一个这样的算法：

• 初始时当前连通块是整棵树。
• 首先，在当前连通块中找到任意一个点 $u$ 作为该次的分治中心（不必是重心）。
• 其次，把点 $u$ 在当前连通块中删去，可以得到若干个连通块。对于每个连通块再递归进行这样的操作。

不难发现，小针从黑心王学长那里学到的点分治在最坏情况下递归层数可以达到 $O(n)$ 层。现在，好奇的小针想要知道，对于一棵给定的包含 $n$ 个节点的树，他有多少种不同的点分治方案呢？因为答案可能很大，你只需要输出它对 $10^9+7$ 取模的值即可。

两种点分治方案不同当且仅当某一个连通块所选的点分治中心不同。

为了避免因为大家所学算法的具体细节不同出现歧义，我们还提供了一份暴力代码（见下发文件中的 show.cpp）来具体描述这个算法。

输入格式

第一行一个整数 $n$ ，表示这棵树的点数。

接下来 $n-1$ 行，每行两个正整数 $x,y$ ,表示点 $x$ 与点 $y$ 之间存在一条边。

点的标号从 $1$ 开始。

输出格式

一行一个整数，表示答案对 $10^9+7$ 取模的值。

样例数据

样例 1 输入

3
1 2
2 3

样例 1 输出

5

样例 1 解释

对于样例一，一共有这五种不同的点分治方案为：

第一层选"1"，第二层选"2"，第三层选"3"。

第一层选"1"，第二层选"3"，第三层选"2"。

第一层选"2"，第二层选"1，3"。

第一层选"3"，第二层选"2"，第三层选"1"。

第一层选"3"，第二层选"1"，第三层选"2"。

样例 2 输入

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

样例 2 输出

78904

子任务

评测使用子任务捆绑。为了拿到某个子任务的分数，你必须通过所有它的每个测试点。

对于所有的数据，有$1\le n \le 5000$，保证给出的是一棵树。

Subtask 1 [5 pts]: $n\le 10$。

Subtask 2 [10 pts]: 保证给定的树是一条链。

Subtask 3 [10 pts]: $n\le 20$。

Subtask 4 [25 pts]: $n\le 60$。

Subtask 5 [20 pts]: $n\le 400$。

Subtask 6 [30 pts]: $n\le 5000$。

提示

为了避免因为大家所学算法的具体细节不同出现歧义，下发文件中提供了代码 show.cpp 来具体描述这个算法。