# tioj 2043 魔法鏈

https://tioj.ck.tp.edu.tw/problems/2043

* 樹dp
* 如果跟節點度數>1，那一定是從葉節點往上拔。事實上根節點度數=1也一樣從下面拔就好，因為我們會枚舉以每個點為根所形成的樹，如此就會發現不用擔心少算從根節點拔的情況了(因為那相當於以其它為根由下往上拔)。
* 如此樹dp的狀態就都一樣了，dp[v]代表把v的子樹都拔完的方法樹(v最後拔)。
* v下面的子樹不能亂拔一通，ex:如果要拔掉某一個child，就要先把那個child下的子樹都拔完才能拔自己。但如果是不同子樹就可以交叉亂拔
* 這時候會發現這其實很像高一下排列組合經典題型，"甲~戊中，丙一定要在甲、乙後面的排列數"。而這個的做法就是把甲乙丙都當作同一個東西做排列，然後再把甲乙隨機排列(2!)。
* 轉移：就照著上述的排列組合題型解法
* 注意要枚舉每個根

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second
#define rep(X, a,b) for(int X=a;X<b;++X)
#define ALL(a) (a).begin(), (a).end()
#define SZ(a) (int)(a).size()
#define NL "\n"
#pragma GCC optimize("Ofast")
using namespace std;
typedef pair<long long,long long> pll;
typedef pair<int,int> pii;
typedef long long ll;

vector<int> adj[2010];
ll res[2010], sz[2010], fact[10000];
const ll mod=1e9+7;
ll fpow(ll a, ll b) {
    ll res = 1;
    while (b > 0) {
        if (b & 1) res = res * a%mod;
        a = a * a%mod;
        b >>= 1;
    }
    return res;
}

void dfs(int v, int p){
    res[v]=sz[v]=1;
    int tot=0;
    for(auto a:adj[v]){
        if(a!=p){
            dfs(a, v);
            sz[v]+=sz[a];
            tot+=sz[a];
        }
    }
    if(sz[v]==1) return;
    res[v]=fact[tot];
    for(auto a:adj[v]) if(a!=p) res[v]=res[v]*fpow(fact[sz[a]], mod-2)%mod*res[a]%mod;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    fact[1]=1;
    rep(i,2,10001) fact[i]=fact[i-1]*i%mod;
    int n, a, b;
    cin>>n;
    rep(i,0,n-1){
        cin>>a>>b;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    ll ans=0;
    rep(i,1,n+1){
        dfs(i, 0);
        ans+=res[i];
        ans%=mod;
    }
    cout<<ans<<NL;
}