#include #include #include #include typedef int32_t i32; typedef int64_t i64; typedef struct directed_edge { int32_t vertex; int32_t next; } graph_edge; typedef struct directedGraph { graph_edge *edge; int32_t *start; int32_t pointer; int32_t vertex_num; int32_t edge_max_size; } graph; graph* new_graph (const int vertex_num) { graph *g = (graph *) calloc (1, sizeof (graph)); g->edge = (graph_edge *) calloc (1, sizeof (graph_edge)); g->start = (int32_t *) calloc (vertex_num, sizeof (int32_t)); g->pointer = 0; g->vertex_num = vertex_num; g->edge_max_size = 1; for (int32_t i = 0; i < vertex_num; ++i) { g->start[i] = -1; } return g; } void add_edge (graph *g, int32_t from, int32_t to) { if (g->pointer == g->edge_max_size) { g->edge_max_size *= 2; g->edge = (graph_edge *) realloc (g->edge, sizeof (graph_edge) * g->edge_max_size); } g->edge[g->pointer] = (graph_edge) {to, g->start[from]}; g->start[from] = g->pointer++; } void BFS_graph (graph *g, int32_t src, i32 *d) { int32_t *q = (int32_t *) calloc (g->vertex_num, sizeof (int32_t)); uint8_t *used = (uint8_t *) calloc (g->vertex_num, sizeof (uint8_t)); int32_t front = 0; int32_t last = 0; used[src] = 1; q[last++] = src; while (front < last) { const int32_t v = q[front++]; for (int32_t p = g->start[v]; p != -1; p = g->edge[p].next) { const int32_t u = g->edge[p].vertex; if (!used[u]) { used[u] = 1; q[last++] = u; d[u] = d[v] + 1; } } } free(q); free(used); } void run (void) { i32 n; scanf ("%" SCNi32, &n); graph *g = new_graph (n); for (i32 i = 1; i < n; ++i) { i32 a, b; scanf ("%" SCNi32 "%" SCNi32, &a, &b); a--; b--; add_edge (g, a, b); add_edge (g, b, a); } i32 *d = (i32 *) calloc (n, sizeof (i32)); BFS_graph (g, 0, d); const i32 mod = 1000000007; i32 *inverse = (i32 *) calloc (n + 1, sizeof (i32)); inverse[1] = 1; for (i32 i = 2; i <= n; ++i) { inverse[i] = (i64) (mod - mod / i) * inverse[mod % i] % mod; } i64 ans = 0;; for (i32 i = 0; i < n; ++i) { i32 x = d[i] + 1; ans += inverse[x]; } ans %= mod; for (i32 i = 1; i <= n; ++i) { ans = (i64) ans * i % mod; } printf ("%" PRIi64 "\n", ans); } int main (void) { run(); return 0; }