#include using namespace std; void gi(int &x){char ch = getchar(); x = 0; while (ch < '0' || ch > '9') ch = getchar(); while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();} const int ljz = 1000000007, ny2 = (ljz + 1) >> 1; void MOD(int &x){if (x >= ljz) x -= ljz; if (x < 0) x += ljz;} int Tm(int x, int y){return (1ll * x * y) % ljz;} int C(int x){return Tm(ny2, Tm(x, x - 1));} int N, sd, sd2, ans, tmp; //sd is the sum of degrees of all paths //sd2 is the sum of (degree**2)s of all paths #define nn 603030 //Arrays below stores the tree. int node[nn], next[nn << 1], to[nn << 1], e; void ins(int x, int y){e++; next[e] = node[x]; node[x] = e; to[e] = y;} int n; int q[nn], par[nn], dep[nn], siz[nn]; //Get subtree sizes rooted at 1 void bfs(){ int i, j, k, l, r; q[l = r = 1] = 1; for (i = 1; i <= n; i++) par[i] = 0; while (l <= r) for (j = node[k = q[l++]]; j; j = next[j]) if (to[j] != par[k]){ par[q[++r] = to[j]] = k; dep[to[j]] = dep[k] + 1; } for (k = q[i = r]; i; i--, k = q[i]) for (siz[k] = 1, j = node[k]; j; j = next[j]) if (to[j] != par[k]) siz[k] += siz[to[j]]; } //using siz[] we can calculate subtree size of c rooted at p, //where (p, c) is in the tree int SIZ(int p, int c) {if (p == par[c]) return siz[c]; else return n - siz[p];} //return zx = centroid and set s = size of connected component int vis[nn]; int Siz[nn], Par[nn]; int get_zx(int x, int &s){ int i, j, k, l, r, zx, zv = 100000000, vv; q[l = r = 1] = x; while (l <= r) for (j = node[k = q[l++]]; j; j = next[j]) if (to[j] != Par[k] && !vis[to[j]]) Par[q[++r] = to[j]] = k; for (i = r; i; i--) { for (k = q[i], Siz[k] = 1, j = node[k], vv = 0; j; j = next[j]) if (to[j] != Par[k] && !vis[to[j]]) Siz[k] += Siz[to[j]], vv = max(vv, Siz[to[j]]); vv = max(vv, r - Siz[k]); if (vv < zv) zv = vv, zx = k; } s = Siz[x]; for (i = 1; i <= r; i++) Siz[q[i]] = Par[q[i]] = 0, q[i] = 0; return zx; } //get() returns size of component and set // Siz[x] = subtree_ways - SIZ(centroid, c), where c is centroid's child and x's ancestor // where subtree_ways is the number of ways to select two nodes in subtree c that the path doesn't intersect with (centroid -- x). // subtree_ways is sum of C(size_of_some_subtree, 2) // sum = sum of Siz[x] // sum2 = sum of Siz[x] ** 2 int get(int x, int &sum, int &sum2){ int i, j, k, l, r; q[l = r = 1] = x; sum = 0; sum2 = 0; while (l <= r) { for (j = node[k = q[l++]]; j; j = next[j]) if (to[j] != Par[k]) MOD(Siz[k] += C(SIZ(k, to[j]))); for (j = node[k]; j; j = next[j]) if (to[j] != Par[k] && !vis[to[j]]) { Par[q[++r] = to[j]] = k; MOD(Siz[to[j]] = Siz[k] - C(SIZ(k, to[j]))); } } for (i = 1; i <= r; i++){ MOD(sum += Siz[q[i]]); MOD(sum2 += Tm(Siz[q[i]], Siz[q[i]])); Siz[q[i]] = Par[q[i]] = 0; } return r; } int szs[nn], smm[nn], smm2[nn]; void dac(int x) { int i, j, k, s, ss = N - 1, l = 0, Smm = 0; //x becomes centroid in x's component x = get_zx(x, s); s--; vis[x] = 1; for (j = node[x]; j; j = next[j]) { if (!vis[to[j]]) { MOD(Siz[to[j]] = -C(SIZ(x, to[j]))); l++; Par[to[j]] = x; szs[l] = get(to[j], smm[l], smm2[l]); MOD(Smm += smm[l]); } MOD(ss -= C(SIZ(x, to[j]))); } //Sum of degree of paths passing x but not ending at x for (i = 1; i <= l; i++) { //sum(ss - Siz[i] - Siz[j]) MOD(sd += Tm(Tm(szs[i], s - szs[i]), Tm(ny2, ss))); MOD(sd -= Tm(smm[i], s - szs[i])); //sum((ss - Siz[i] - Siz[j]) ** 2 // = ss**2 + Siz[i]**2 + Siz[j]**2 - 2*ss*Siz[i] - 2*ss*Siz[j] + 2*Siz[i]*Siz[j]) MOD(sd2 += Tm(Tm(szs[i], s - szs[i]), Tm(ny2, Tm(ss, ss)))); MOD(sd2 += Tm(smm2[i], s - szs[i])); MOD(sd2 -= Tm(smm[i], Tm(2, Tm(ss, s - szs[i])))); MOD(sd2 += Tm(smm[i], Smm - smm[i])); } //Sum of degrees ending at x //sum(ss - Siz[x]) MOD(sd += Tm(ss, s)); for (i = 1; i <= l; i++) MOD(sd -= smm[i]); //sum(ss**2 + Siz[x]**2 - 2*ss*Siz[x]) MOD(sd2 += Tm(Tm(ss, ss), s)); for (i = 1; i <= l; i++){ MOD(sd2 += smm2[i]); MOD(sd2 -= Tm(ss, Tm(2, smm[i]))); } for (j = node[x]; j; j = next[j]) if (!vis[to[j]]) dac(to[j]); } int main(){ int i, a, b; gi(n); N = C(n); for (i = 1; i < n; i++) {gi(a); gi(b); ins(a, b); ins(b, a);} bfs(); dac(1); //sd and sd2 calculated. MOD(ans = Tm(ny2, sd2 - Tm(N - 1, sd))); tmp = Tm(Tm(N, N - 1), Tm(N - 2, (ljz + 1) / 6)); MOD(ans += tmp); printf("%d\n", ans); return 0; }