/* -*- coding: utf-8 -*- * * 1103.cc: No.1103 Directed Length Sum - yukicoder */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; /* constant */ const int MAX_N = 1000000; const int MOD = 1000000007; /* typedef */ typedef queue qi; /* global variables */ int ps[MAX_N], ss[MAX_N], cns[MAX_N], fss[MAX_N]; /* subroutines */ /* main */ int main() { int n; scanf("%d", &n); memset(ps, -1, sizeof(ps)); for (int i = 1; i < n; i++) { int a, b; scanf("%d%d", &a, &b); a--, b--; ps[b] = a, cns[a]++; } qi q; for (int u = 0; u < n; u++) if (cns[u] == 0) q.push(u); while (! q.empty()) { int u = q.front(); q.pop(); int up = ps[u]; ss[u]++; if (up >= 0) { ss[up] += ss[u]; fss[up] = (fss[up] + (fss[u] + ss[u]) % MOD) % MOD; if (--cns[up] == 0) q.push(up); } } //for (int i = 0; i < n; i++) printf("%d ", fss[i]); putchar('\n'); int sum = 0; for (int i = 0; i < n; i++) sum = (sum + fss[i]) % MOD; printf("%d\n", sum); return 0; }