7. Šibalské sny vzorové riešenie

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll MXN = 10111;
const ll MOD = 1000000007;
ll TC, n, a, b;
vector<vector<ll>> G;
map<vector<ll>, ll> ids_by_children; // Tymto namapujeme usporiadane pole id-ciek deti na id aktualneho vrchola
vector<ll> vertex_ids, ways, fact;

void calc_fact() {
    fact.clear();
    fact.push_back(1);
    for(ll i = 1; i < MXN; i++)
        fact.push_back((fact[i - 1] * i) % MOD);
}

// Umocnovanie q^x v O(log x) s modulovanim
ll expo(ll q, ll x) {
    if(x == 0)
        return 1LL;
    if(x == 1)
        return q;
    ll base = expo((q * q) % MOD, x / 2);
    if(x & 1LL)
        base = (base * q) % MOD;
    return base % MOD;
}

void dfs(ll u, ll p) {
    vector<ll> child_ids;
    map<ll, ll> cnt;
    for(int i = 0; i < G[u].size(); i++) {
        ll v = G[u][i];
        if(v != p) {
            dfs(v, u);
            child_ids.push_back(vertex_ids[v]);
            cnt[vertex_ids[v]]++;
        }
    }
    sort(child_ids.begin(), child_ids.end());
    bool done = true; // Ci sme uz pridelili id aktualnemu child_ids
    if(ids_by_children.find(child_ids) == ids_by_children.end()) {
        ids_by_children[child_ids] = ids_by_children.size(); // Pridelime sekvencne dalsie id
        done = false; // Ak sme uz davnejsie nepridelili id, tak este nemame zratane ways, tak si to poznacime
    }
    vertex_ids[u] = ids_by_children[child_ids];
    if(!done) {
        // Pouzijeme sucin zo vzoraku
        for (auto &x: cnt) {
            ways[vertex_ids[u]] *= (fact[x.second] * expo(ways[x.first], x.second)) % MOD;
            ways[vertex_ids[u]] %= MOD;
        }
    }
}

int main() {
    calc_fact(); // Predpocitame si faktorialy % MOD
    cin >> TC;
    while(TC--) {
        cin >> n;
        G.clear();
        G.resize(n);
        for(int i = 0; i < n - 1; i++) {
            cin >> a >> b;
            G[a].push_back(b);
            G[b].push_back(a);
        }
        ids_by_children.clear();
        ways.assign(n + 1, 1);
        vertex_ids.assign(n, -1);
        dfs(0, -1);
        cout << ways[vertex_ids[0]] << '\n'; // Koren je 0
    }

    return 0;
}

import sys

sys.setrecursionlimit(1000000)

MXN = 10111
MOD = 10**9 + 7
fact = [1]


# Logaritmicke umocnovanie q^x s modulovanim
# Da sa namiesto toho pouzit funkcia pow
def expo(q, x):
    if x == 0:
        return 1
    if x == 1:
        return q
    base = expo((q * q) % MOD, x // 2)
    if x % 2 == 1:
        base = (base * q) % MOD
    return base % MOD


def dfs(u, p, G, ids_by_children, vertex_ids, ways):
    child_ids = []
    cnt = {}
    for i in range(len(G[u])):
        v = G[u][i]
        if v != p:
            dfs(v, u, G, ids_by_children, vertex_ids, ways)
            child_ids.append(vertex_ids[v])
            if vertex_ids[v] not in cnt:
                cnt[vertex_ids[v]] = 0
            cnt[vertex_ids[v]] += 1
    child_ids = tuple(sorted(child_ids))  # Usporiadanie pole id-ciek deti
    done = True  # Ci sme uz aktualnemu child_ids pridelili id niekedy davnejsie
    if child_ids not in ids_by_children:
        ids_by_children[child_ids] = len(ids_by_children)  # Sekvencne pridelime dalsie id
        done = False  # Este sme nepridelili, musime to spravit v dalsich par riadkoch
    vertex_ids[u] = ids_by_children[child_ids]
    if not done:
        # Pouzijeme sucin zo vzoraku
        for k, v in cnt.items():
            ways[vertex_ids[u]] *= (fact[v] * expo(ways[k], v)) % MOD
            ways[vertex_ids[u]] %= MOD


# Predpocitame si faktorialy % MOD
for i in range(MXN):
    fact.append((fact[i] * (i + 1)) % MOD)

TC = int(input())

for tc in range(TC):
    ids_by_children = {}
    n = int(input())
    G = [[] for _ in range(n)]
    for i in range(n - 1):
        a, b = [int(x) for x in input().split()]
        G[a].append(b)
        G[b].append(a)
    ways = [1] * n
    vertex_ids = [-1] * n
    dfs(0, -1, G, ids_by_children, vertex_ids, ways)
    print(ways[vertex_ids[0]])  # Koren je 0