// ---------- begin graph ---------- struct Graph { size: usize, edge: Vec<(usize, usize, T)>, graph: Vec<(usize, T)>, start: Vec, length: Vec, ini: T, } #[allow(dead_code)] impl Graph { fn new(size: usize, ini: T) -> Self { Graph { size: size, edge: vec![], graph: Vec::with_capacity(size), start: Vec::with_capacity(size), length: Vec::with_capacity(size), ini: ini, } } fn add_edge(&mut self, src: usize, dst: usize, val: T) { assert!(src < self.size && dst < self.size); self.edge.push((src, dst, val)); } fn build(&mut self) { let size = self.size; self.length.clear(); self.length.resize(size, 0); for e in self.edge.iter() { self.length[e.0] += 1; } self.start.clear(); let mut sum = 0; for d in self.length.iter() { sum += *d; self.start.push(sum); } assert!(self.edge.len() == sum); self.graph.clear(); self.graph.resize(self.edge.len(), (size, self.ini.clone())); while let Some((src, dst, val)) = self.edge.pop() { self.start[src] -= 1; let k = self.start[src]; self.graph[k] = (dst, val); } assert!(self .start .windows(2) .zip(self.length.iter()) .all(|(s, l)| s[1] - s[0] == *l)); assert!(*self.start.last().unwrap() + *self.length.last().unwrap() == self.graph.len()); // } } // remove と銘打っているが実際に要素は削除されないので注意 fn remove(&mut self, v: usize, k: usize) { assert!(v < self.size && k < self.length[v]); let s = self.start[v]; let len = self.length[v]; self.graph.swap(s + k, s + len - 1); self.length[v] -= 1; } } impl std::ops::Index for Graph { type Output = [(usize, T)]; fn index(&self, v: usize) -> &Self::Output { let len = self.length[v]; let s = self.start[v]; &self.graph[s..(s + len)] } } impl std::ops::IndexMut for Graph { fn index_mut(&mut self, v: usize) -> &mut Self::Output { let len = self.length[v]; let s = self.start[v]; &mut self.graph[s..(s + len)] } } // ---------- end graph ---------- // ---------- begin Scanner(require delimiter) ---------- mod scanner { pub struct Scanner { reader: R, buf: Vec, } #[allow(dead_code)] impl Scanner { pub fn new(reader: R) -> Self { Scanner { reader: reader, buf: Vec::with_capacity(1024), } } fn read(&mut self, del: u8) { self.buf.clear(); self.reader.read_until(del, &mut self.buf).ok(); assert!(self.buf.pop().unwrap() == del); } pub fn next(&mut self, del: u8) -> T { self.read(del); std::str::from_utf8(&self.buf) .unwrap() .trim() .parse::() .ok() .unwrap() } pub fn next_bytes(&mut self, del: u8) -> Vec { self.read(del); std::str::from_utf8(&self.buf) .unwrap() .trim() .bytes() .collect() } } } // ---------- end scanner(require delimiter) ---------- fn main() { let stdin = std::io::stdin(); let mut sc = scanner::Scanner::new(stdin.lock()); run(&mut sc); } fn run(sc: &mut scanner::Scanner) { let n: usize = sc.next(b'\n'); let mut g = Graph::new(n, ()); let mut child = vec![false; n]; for _ in 1..n { let a: usize = sc.next(b' '); let b: usize = sc.next(b'\n'); g.add_edge(a - 1, b - 1, ()); child[b - 1] = true; } g.build(); let root = child.into_iter().position(|p| !p).unwrap(); let mut q = vec![root]; for i in 0..n { let v = q[i]; for &(u, _) in g[v].iter() { q.push(u); } } let mut ans = 0u64; let mut dp = vec![(0, 0); n]; for &v in q.iter().rev() { let mut val = (0u64, 1u64); for &(u, _) in g[v].iter() { let p = &dp[u]; val.0 += p.0 + p.1; val.1 += p.1; } ans += val.0; dp[v] = val; } println!("{}", ans % 1_000_000_007); }