#include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; #define int long long #define double long double typedef vector VI; typedef pair pii; typedef vector VP; typedef vector VS; typedef priority_queue PQ; templatebool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; } templatebool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; } #define fore(i,a) for(auto &i:a) #define REP(i,n) for(int i=0;i, greater > q2; int N; int ans[1000010]; VI G[1000010]; int t[1000010];//size of subtree void dfs(int now, int pa) { int res = 0; fore(to, G[now]) { dfs(to, now); res += t[to] + ans[to]; res %= mod; } ans[now] = res; } void dfs1(int now, int pa) { fore(to, G[now]) { if (to == pa)continue; dfs1(to, now); } t[now]++; if (pa != -1)t[pa] += t[now]; return; } signed main() { cin.tie(0); ios::sync_with_stdio(false); cin >> N; vectorF(N, false); REP(i, N - 1) { int a, b; cin >> a >> b; a--; b--; G[a].push_back(b); F[b] = 1; } int root; REP(i, N)if (!F[i])root = i; dfs1(root, -1); dfs(root, -1); int sum = 0; REP(i, N) { sum += ans[i]; sum %= mod; } cout << sum << endl; return 0; }