fn main() { let mut io = IO::new(); let n = io.scan(); if n == 1 { io.println(0); return; } let ed: Vec<(usize, usize, i64)> = io.scan_vec(n-1); type Fp = F1000000007; let mut g = UndirectedGraph::new(n); for &(u, v, w) in &ed { g.add_edge(u - 1, v - 1, w); } let root = (0..n).filter(|&i| g.edges_from(i).count() == 1).next().unwrap(); let (dist, par, euler, size) = tree_dfs(&g, root); let dist = dist.into_iter().map(|x| Fp::new(x)).collect::>(); let size = size.into_iter().map(|x| Fp::new(x as i64)).collect::>(); let score = (0..n).map(|v| if par[v].is_none() { Fp::zero() } else { dist[v] - dist[par[v].unwrap()] }).collect::>(); let fpn = Fp::new(n as i64); let mut tsum = vec![Fp::zero(); n]; let mut bsum = vec![Fp::zero(); n]; for &v in euler.iter().skip(2).rev() { let u = par[v].unwrap(); bsum[u] = bsum[u] + bsum[v] + score[v] * size[v]; } for &v in euler.iter().skip(2) { let u = par[v].unwrap(); tsum[v] = tsum[u] + score[u] * (fpn - size[u]) + bsum[u] - bsum[v] - score[v] * size[v]; } let mut ans = Fp::zero(); for &v in euler.iter().skip(1) { ans += score[v] * score[v] * size[v] * (fpn - size[v]) + tsum[v] * score[v] * size[v] + bsum[v] * score[v] * (fpn - size[v]); } println!("{}", ans); } pub fn tree_dfs>(g: &G, root: usize) -> (Vec, Vec>, Vec, Vec) { let n = g.size(); let mut euler = Vec::with_capacity(n); let mut dist = vec![C::MAX; n]; dist[root] = C::zero(); let mut par = vec![None; n]; let mut size = vec![1; n]; let mut q = vec![root]; while let Some(v) = q.pop() { euler.push(v); for e in g.edges_from(v) { if par[v] == Some(e.to) { continue; } par[e.to] = Some(v); dist[e.to] = dist[v] + e.cost; q.push(e.to); } } for &i in euler.iter().skip(1).rev() { size[par[i].unwrap()] += size[i]; } (dist, par, euler, size) } // ------------ fp start ------------ use std::{ fmt::{Debug, Display}, hash::Hash, iter, marker::PhantomData, }; // NOTE: `crate::` がないとうまく展開できません。 crate::define_fp!(pub F998244353, Mod998244353, 998244353); crate::define_fp!(pub F1000000007, Mod1000000007, 1000000007); #[derive(Clone, PartialEq, Copy, Eq, Hash)] pub struct Fp(i64, PhantomData); pub trait Mod: Debug + Clone + PartialEq + Copy + Eq + Hash { const MOD: i64; } impl Fp { pub fn new(mut x: i64) -> Self { x %= T::MOD; Self::unchecked(if x < 0 { x + T::MOD } else { x }) } pub fn into_inner(self) -> i64 { self.0 } pub fn r#mod() -> i64 { T::MOD } pub fn inv(self) -> Self { assert_ne!(self.0, 0, "Zero division"); let (sign, x) = if self.0 * 2 < T::MOD { (1, self.0) } else { (-1, T::MOD - self.0) }; let (g, _a, b) = ext_gcd(T::MOD, x); let ans = sign * b; assert_eq!(g, 1); Self::unchecked(if ans < 0 { ans + T::MOD } else { ans }) } pub fn frac(x: i64, y: i64) -> Self { Fp::new(x) / Fp::new(y) } pub fn pow(mut self, mut p: u64) -> Self { let mut ans = Fp::new(1); while p != 0 { if p & 1 == 1 { ans *= self; } self *= self; p >>= 1; } ans } fn unchecked(x: i64) -> Self { Self(x, PhantomData) } } impl iter::Sum> for Fp { fn sum(iter: I) -> Self where I: iter::Iterator>, { iter.fold(Fp::new(0), Add::add) } } impl<'a, T: 'a + Mod> iter::Sum<&'a Fp> for Fp { fn sum(iter: I) -> Self where I: iter::Iterator>, { iter.fold(Fp::new(0), Add::add) } } impl iter::Product> for Fp { fn product(iter: I) -> Self where I: iter::Iterator>, { iter.fold(Self::new(1), Mul::mul) } } impl<'a, T: 'a + Mod> iter::Product<&'a Fp> for Fp { fn product(iter: I) -> Self where I: iter::Iterator>, { iter.fold(Self::new(1), Mul::mul) } } impl Debug for Fp { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> { write!(f, "{}", self.0) } } impl Display for Fp { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> { write!(f, "{}", self.0) } } // ax + by = gcd(x, y) なる、互いに素な (a, b) を一組探して、(g, a, b) を返します。 // // | 0 -x | | y -x | | x 0 | // | 1 b | = | a b | | y 1 | fn ext_gcd(x: i64, y: i64) -> (i64, i64, i64) { let (b, g) = { let mut x = x; let mut y = y; let mut u = 0; let mut v = 1; while x != 0 { let q = y / x; y -= q * x; v -= q * u; std::mem::swap(&mut x, &mut y); std::mem::swap(&mut u, &mut v); } (v, y) }; assert_eq!((g - b * y) % x, 0); let a = (g - b * y) / x; (g, a, b) } #[macro_export] macro_rules! define_fp { ($vis:vis $fp:ident, $t:ident, $mod:expr) => { #[derive(Debug, Clone, PartialEq, Copy, Eq, Hash)] $vis struct $t; // NOTE: `$crate::` があるとうまく展開できません。 impl Mod for $t { const MOD: i64 = $mod; } // NOTE: `$crate::` があるとうまく展開できません。 $vis type $fp = Fp<$t>; } } // ------------ impl arith start ------------ impl Associative for Fp {} impl Zero for Fp { fn zero() -> Self { Self::unchecked(0) } fn is_zero(&self) -> bool { self.0 == 0 } } impl One for Fp { fn one() -> Self { Self::unchecked(1) } fn is_one(&self) -> bool { self.0 == 1 } } impl Add for Fp { type Output = Self; fn add(self, rhs: Self) -> Self { let res = self.0 + rhs.0; Self::unchecked(if T::MOD <= res { res - T::MOD } else { res }) } } impl Sub for Fp { type Output = Self; fn sub(self, rhs: Self) -> Self { let res = self.0 - rhs.0; Self::unchecked(if res < 0 { res + T::MOD } else { res }) } } impl Mul for Fp { type Output = Self; fn mul(self, rhs: Self) -> Self { Self::new(self.0 * rhs.0) } } #[allow(clippy::suspicious_arithmetic_impl)] impl Div for Fp { type Output = Self; fn div(self, rhs: Self) -> Self { self * rhs.inv() } } impl Neg for Fp { type Output = Self; fn neg(self) -> Self { if self.0 == 0 { Self::unchecked(0) } else { Self::unchecked(M::MOD - self.0) } } } impl Neg for &Fp { type Output = Fp; fn neg(self) -> Self::Output { if self.0 == 0 { Fp::unchecked(0) } else { Fp::unchecked(M::MOD - self.0) } } } macro_rules! forward_assign_biop { ($(impl $trait:ident, $fn_assign:ident, $fn:ident)*) => { $( impl $trait for Fp { fn $fn_assign(&mut self, rhs: Self) { *self = self.$fn(rhs); } } )* }; } forward_assign_biop! { impl AddAssign, add_assign, add impl SubAssign, sub_assign, sub impl MulAssign, mul_assign, mul impl DivAssign, div_assign, div } macro_rules! forward_ref_binop { ($(impl $imp:ident, $method:ident)*) => { $( impl<'a, T: Mod> $imp> for &'a Fp { type Output = Fp; fn $method(self, other: Fp) -> Self::Output { $imp::$method(*self, other) } } impl<'a, T: Mod> $imp<&'a Fp> for Fp { type Output = Fp; fn $method(self, other: &Fp) -> Self::Output { $imp::$method(self, *other) } } impl<'a, T: Mod> $imp<&'a Fp> for &'a Fp { type Output = Fp; fn $method(self, other: &Fp) -> Self::Output { $imp::$method(*self, *other) } } )* }; } forward_ref_binop! { impl Add, add impl Sub, sub impl Mul, mul impl Div, div } // ------------ impl arith end ------------ // ------------ fp end ------------ // ------------ algebraic traits start ------------ use std::marker::Sized; use std::ops::*; /// 元 pub trait Element: Sized + Clone + PartialEq {} impl Element for T {} /// 結合性 pub trait Associative: Magma {} /// マグマ pub trait Magma: Element + Add {} impl> Magma for T {} /// 半群 pub trait SemiGroup: Magma + Associative {} impl SemiGroup for T {} /// モノイド pub trait Monoid: SemiGroup + Zero {} impl Monoid for T {} pub trait ComMonoid: Monoid + AddAssign {} impl ComMonoid for T {} /// 群 pub trait Group: Monoid + Neg {} impl> Group for T {} pub trait ComGroup: Group + ComMonoid {} impl ComGroup for T {} /// 半環 pub trait SemiRing: ComMonoid + Mul + One {} impl + One> SemiRing for T {} /// 環 pub trait Ring: ComGroup + SemiRing {} impl Ring for T {} pub trait ComRing: Ring + MulAssign {} impl ComRing for T {} /// 体 pub trait Field: ComRing + Div + DivAssign {} impl + DivAssign> Field for T {} /// 加法単元 pub trait Zero: Element { fn zero() -> Self; fn is_zero(&self) -> bool { *self == Self::zero() } } /// 乗法単元 pub trait One: Element { fn one() -> Self; fn is_one(&self) -> bool { *self == Self::one() } } macro_rules! impl_integer { ($($T:ty,)*) => { $( impl Associative for $T {} impl Zero for $T { fn zero() -> Self { 0 } fn is_zero(&self) -> bool { *self == 0 } } impl<'a> Zero for &'a $T { fn zero() -> Self { &0 } fn is_zero(&self) -> bool { *self == &0 } } impl One for $T { fn one() -> Self { 1 } fn is_one(&self) -> bool { *self == 1 } } impl<'a> One for &'a $T { fn one() -> Self { &1 } fn is_one(&self) -> bool { *self == &1 } } )* }; } impl_integer! { i8, i16, i32, i64, i128, isize, u8, u16, u32, u64, u128, usize, } // ------------ algebraic traits end ------------ // ------------ Graph impl start ------------ pub trait Cost: Element + Clone + Copy + std::fmt::Display + Eq + Ord + Zero + One + Add + AddAssign + Sub + Neg { const MAX: Self; } #[derive(Copy, Clone)] pub struct Edge { // pub from: usize, pub to: usize, pub cost: C, pub id: usize } pub struct UndirectedGraph(pub Vec>>, pub usize); pub struct DirectedGraph{ pub forward: Vec>>, pub backward: Vec>>, pub count: usize, } pub trait Graph { fn new(size: usize) -> Self; fn size(&self) -> usize; fn add_edge(&mut self, u: usize, v: usize, cost: C); fn edges_from(&self, v: usize) -> std::slice::Iter>; } impl Graph for UndirectedGraph { fn new(size: usize) -> Self { Self(vec![Vec::>::new(); size], 0) } fn size(&self) -> usize { self.0.len() } fn add_edge(&mut self, u: usize, v: usize, cost: C) { self.0[u].push(Edge{ to: v, cost: cost.clone(), id: self.1 }); self.0[v].push(Edge{ to: u, cost: cost.clone(), id: self.1 }); self.1 += 1; } fn edges_from(&self, v: usize) -> std::slice::Iter> { self.0[v].iter() } } impl Graph for DirectedGraph { fn new(size: usize) -> Self { Self { forward: vec![Vec::>::new(); size], backward: vec![Vec::>::new(); size], count: 0 } } fn size(&self) -> usize { self.forward.len() } fn add_edge(&mut self, u: usize, v: usize, cost: C) { self.forward[u].push(Edge{ to: v, cost: cost.clone(), id: self.count }); self.backward[v].push(Edge{ to: u, cost: cost.clone(), id: self.count }); self.count += 1; } fn edges_from(&self, v: usize) -> std::slice::Iter> { self.forward[v].iter() } } impl DirectedGraph { pub fn edges_to(&self, u: usize) -> std::slice::Iter> { self.backward[u].iter() } pub fn reverse(&self) -> Self { Self { forward: self.backward.clone(), backward: self.forward.clone(), count: self.count, } } } macro_rules! impl_cost { ($($T:ident,)*) => { $( impl Cost for $T { const MAX: Self = std::$T::MAX; } )* }; } impl_cost! { i8, i16, i32, i64, i128, isize, } #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord)] pub struct Void(); impl std::fmt::Display for Void { fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result { write!(f, "") } } impl Zero for Void { fn zero() -> Self { Void() } fn is_zero(&self) -> bool { true } } impl One for Void { fn one() -> Self { Void() } fn is_one(&self) -> bool { true } } impl Add for Void { type Output = Self; fn add(self, _: Self) -> Self { Void() } } impl AddAssign for Void { fn add_assign(&mut self, _: Self) {} } impl Sub for Void { type Output = Self; fn sub(self, _: Self) -> Self { Void() } } impl Neg for Void { type Output = Self; fn neg(self) -> Self { Void() } } impl Cost for Void { const MAX: Self = Void(); } // ------------ Graph impl end ------------ // ------------ io module start ------------ use std::io::{stdout, BufWriter, Read, StdoutLock, Write}; pub struct IO { iter: std::str::SplitAsciiWhitespace<'static>, buf: BufWriter>, } impl IO { pub fn new() -> Self { let mut input = String::new(); std::io::stdin().read_to_string(&mut input).unwrap(); let input = Box::leak(input.into_boxed_str()); let out = Box::new(stdout()); IO { iter: input.split_ascii_whitespace(), buf: BufWriter::new(Box::leak(out).lock()), } } fn scan_str(&mut self) -> &'static str { self.iter.next().unwrap() } fn scan_raw(&mut self) -> &'static [u8] { self.scan_str().as_bytes() } pub fn scan(&mut self) -> T { T::scan(self) } pub fn scan_vec(&mut self, n: usize) -> Vec { (0..n).map(|_| self.scan()).collect() } } impl IO { pub fn print(&mut self, x: T) { T::print(self, x); } pub fn println(&mut self, x: T) { self.print(x); self.print("\n"); } pub fn iterln>(&mut self, mut iter: I, delim: &str) { if let Some(v) = iter.next() { self.print(v); for v in iter { self.print(delim); self.print(v); } } self.print("\n"); } pub fn flush(&mut self) { self.buf.flush().unwrap(); } } impl Default for IO { fn default() -> Self { Self::new() } } pub trait Scan { fn scan(io: &mut IO) -> Self; } macro_rules! impl_parse_int { ($($t:tt),*) => { $( impl Scan for $t { fn scan(s: &mut IO) -> Self { let mut res = 0; let mut neg = false; for d in s.scan_raw() { if *d == b'-' { neg = true; } else { res *= 10; res += (*d - b'0') as $t; } } if neg { res = res.wrapping_neg(); } res } } )* }; } impl_parse_int!(i16, i32, i64, isize, u16, u32, u64, usize); impl Scan for (T, U) { fn scan(s: &mut IO) -> Self { (T::scan(s), U::scan(s)) } } impl Scan for (T, U, V) { fn scan(s: &mut IO) -> Self { (T::scan(s), U::scan(s), V::scan(s)) } } impl Scan for (T, U, V, W) { fn scan(s: &mut IO) -> Self { (T::scan(s), U::scan(s), V::scan(s), W::scan(s)) } } pub trait Print { fn print(w: &mut IO, x: Self); } macro_rules! impl_print_int { ($($t:ty),*) => { $( impl Print for $t { fn print(w: &mut IO, x: Self) { w.buf.write_all(x.to_string().as_bytes()).unwrap(); } } )* }; } impl_print_int!(i16, i32, i64, isize, u16, u32, u64, usize); impl Print for u8 { fn print(w: &mut IO, x: Self) { w.buf.write_all(&[x]).unwrap(); } } impl Print for &[u8] { fn print(w: &mut IO, x: Self) { w.buf.write_all(x).unwrap(); } } impl Print for &str { fn print(w: &mut IO, x: Self) { w.print(x.as_bytes()); } } impl Print for (T, U) { fn print(w: &mut IO, (x, y): Self) { w.print(x); w.print(" "); w.print(y); } } impl Print for (T, U, V) { fn print(w: &mut IO, (x, y, z): Self) { w.print(x); w.print(" "); w.print(y); w.print(" "); w.print(z); } } // ------------ io module end ------------