#include struct FastIO { char buf[20000000]; char *ptr = buf; void read() { int size; size = fread(buf, 1, sizeof(buf) - 1, stdin); buf[size] = '\0'; ptr = buf; } FastIO () { read(); } void inc() { ptr++; // if (++ptr == buf + sizeof(buf) || !*ptr) read(); } template Integer read() { bool neg = false; Integer res = 0; while ((*ptr < '0' || *ptr > '9') && *ptr != '-') inc(); if (*ptr == '-') neg = true, inc(); while (*ptr >= '0' && *ptr <= '9') res = res * 10 + *ptr - '0', inc(); return neg ? -res : res; } } fastio; #define ri fastio.read #define rs64 fastio.read std::vector > hen; int main() { int n = ri(); std::pair hens[n - 1]; for (int i = 0; i + 1 < n; i++) { hens[i].first = ri() - 1; hens[i].second = ri() - 1; } clock_t r0 = clock(); int degree[n]; memset(degree, 0, sizeof(degree)); bool used[n]; memset(used, 0, sizeof(used)); for (int i = 0; i + 1 < n; i++) { degree[hens[i].first]++; used[hens[i].second] = true; } int root = std::find(used, used + n, 0) - used; hen.resize(n); for (int i = 0; i < n; i++) hen[i].resize(degree[i]); for (auto i : hens) hen[i.first][--degree[i.first]] = i.second; int64_t res = 0; static int que[2][1000000]; static int head[2]; que[0][head[0]++] = root; for (int i = 0; head[i & 1]; i++) { res += (int64_t) i * (i + 1) / 2 * head[i & 1]; int next = (i ^ 1) & 1; head[next] = 0; for (int j = 0; j < head[i & 1]; j++) { memcpy(que[next] + head[next], &hen[que[i & 1][j]][0], sizeof(int) * hen[que[i & 1][j]].size()); head[next] += hen[que[i & 1][j]].size(); } } printf("%d\n", (int) (res % 1000000007)); clock_t r1 = clock(); fprintf(stderr, "took %f ms\n", (double)(r1 - r0) / CLOCKS_PER_SEC * 1000); return 0; }