#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #ifdef LOCAL #define eprintf(...) fprintf(stderr, __VA_ARGS__) #else #define eprintf(...) 42 #endif #define rep_(i, a_, b_, a, b, ...) for (int i = (a), i##_len = (b); i < i##_len; ++i) #define rep(i, ...) rep_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__) #define reprev_(i, a_, b_, a, b, ...) for (int i = (b-1), i##_min = (a); i >= i##_min; --i) #define reprev(i, ...) reprev_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__) #define all(x) (x).begin(), (x).end() template bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; } template bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; } // template T gcd(T a, T b) { return b ? gcd(b, a % b) : a; } using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair P; typedef long double ld; int main (void) { cin.tie(0); ios::sync_with_stdio(false); int n; cin >> n; vector parent(n, -1); vector

e(n - 1); vector> graph(n); rep (i, n - 1) { cin >> e[i].first >> e[i].second; e[i].first--; e[i].second--; graph[e[i].first].push_back(e[i].second); parent[e[i].second] = e[i].first; } int top; rep (i, n) { if (parent[i] == -1) { top = i; break; } } ll MOD = (ll)1e9 + 7; vector num(n), depth(n); vector used(n); stack st; st.push(top); while (!st.empty()) { int a = st.top(); eprintf("%d ", a); if (!used[a] && !graph[a].empty()) { for (int i : graph[a]) { st.push(i); depth[i] = depth[a] + 1; } used[a] = true; } else { num[a]++; for (int i : graph[a]) num[a] = (num[a] + num[i]) % MOD; st.pop(); } } eprintf("\n"); ll ans = 0; rep (i, n) eprintf("%lld%c", num[i], " \n"[i == i_len - 1]); rep (i, n) eprintf("%lld%c", depth[i], " \n"[i == i_len - 1]); rep (i, n) if (i != top) ans = (ans + num[i] * depth[i]) % MOD; cout << ans << "\n"; return 0; }