小吨的点分治
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

有一天，小吨向火山哥请教了点分治的写法。火山哥教了小吨如下的点分治算法:
  • 初始时当前连通块是整棵树。
  • 首先，在当前连通块中找到任意一个点 作为该次的分治中心（不必是重心）。
  • 其次，把点  在当前连通块中删去，可以得到若干个连通块。对于每个连通块再递归进行这样的操作。
不难发现，小吨从黑心火山哥那里学到的点分治在最坏情况下递归层数可以达到 层。现在，好奇的小吨想要知道，对于一棵给定的包含 个节点的树，他有多少种不同的点分治方案呢？因为答案可能很大，你只需要输出它对 取模的值即可。
两种点分治方案不同当且仅当某一个连通块所选的点分治中心不同。
为了避免因为大家所学算法的具体细节不同出现歧义，我们还提供了一份暴力代码来具体描述这个算法。 
const int mod=1e9+7;
const int maxn=5005;
bool vis[maxn];
vector<int> e[maxn];
int n;
inline void view_all(vector<int> &cur,int x,int fa){
    cur.push_back(x);
    for(int p: e[x]){
        if (vis[p]) continue;
        if (p == fa) continue;
        view_all(cur, p, x);
    }
}
inline int calc(int x){
    vector<int> cur;
    int ans = 0;
    view_all(cur, x, -1);
    for(int w: cur){
        int res = 1;
        vis[w] = 1;
        for(int p: e[w]){
            if (vis[p]) continue;
            res = 1ll * res * calc(p) % mod;
        }
        vis[w] = 0;
        ans = (ans + res) % mod;
    }
    return ans;
}
inline int get_ans(){
    return calc(1);
}

输入描述:

第一行一个整数  ，表示这棵树的点数。
接下来  行，每行两个正整数  ,表示点  与点  之间存在一条边。
点的标号从  开始。
,保证给出的是一棵树。

输出描述:

一行一个整数，表示答案对  取模的值。
示例1

输入

复制 
3
1 2
2 3

输出

复制 
5
示例2

输入

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

输出

复制 
78904

备注:

对于样例一，一共有这五种不同的点分治方案为：
第一层选"1"，第二层选"2"，第三层选"3"。
第一层选"1"，第二层选"3"，第三层选"2"。
第一层选"2"，第二层选"1，3"。
第一层选"3"，第二层选"2"，第三层选"1"。
第一层选"3"，第二层选"1"，第三层选"2"。