use std::collections::{VecDeque, HashSet}; const DIVISOR: usize = 1_000_000_007; fn dfs(path: &mut Vec>, index: usize, result: &mut VecDeque, checked: &mut HashSet) { if checked.contains(&index) { return; } while let Some(next) = path[index].pop_front() { dfs(path, next, result, checked); } checked.insert(index); result.push_front(index); } fn topological_sort(path: &mut Vec>) -> VecDeque { let mut result: VecDeque = VecDeque::new(); let mut checked: HashSet = HashSet::new(); let limit = path.len(); for i in 0..limit { dfs(path, i, &mut result, &mut checked); } result } fn calc(path: &mut Vec>, index: usize, depth: &mut usize) -> usize { if path[index].is_empty() { return *depth * (*depth + 1) / 2 % DIVISOR; } let mut flg = false; let mut result: usize = 0; while let Some(next) = path[index].pop_front() { *depth += 1; let val = calc(path, next, depth); *depth -= 1; result += val; if !flg { result += *depth * (*depth + 1) / 2; flg = true; } result %= DIVISOR; } result % DIVISOR } fn main() { let mut n = String::new(); std::io::stdin().read_line(&mut n).ok(); let n: usize = n.trim().parse().unwrap(); let mut path: Vec> = vec![VecDeque::new(); n]; for _ in 0..n-1 { let mut ab = String::new(); std::io::stdin().read_line(&mut ab).ok(); let ab: Vec = ab.trim().split_whitespace().map(|s| s.parse::().unwrap() - 1usize).collect(); path[ab[0]].push_back(ab[1]); } let mut path_data = path.clone(); let mut sorted_indices = topological_sort(&mut path); let parent = sorted_indices.pop_front().unwrap(); let mut depth: usize = 0; println!("{}", calc(&mut path_data, parent, &mut depth)); }