fn main() { let mut io = IO::new(); input!{ from io, n: usize, m: usize, k: i64, mut ed: [(Usize1, Usize1, i64); m] } let mut g = UndirectedGraph::new(n); kruskal(&mut g, &mut ed); let (dist, par, size, _) = tree_dfs(&g, 0); let mut ans = 0; for i in 1..n { let z = dist[i] - dist[par[i].unwrap()]; ans += modpow(k, z, MOD) * size[i] as i64 * (n - size[i]) as i64 % MOD; } io.println(ans % MOD); } const MOD: i64 = 1_000_000_007; pub fn modpow(mut x: i64, mut y: i64, modulo: i64) -> i64 { x %= modulo; if x == 0 { return 0; } let mut ret = 1; let mut cur = x; while y > 0 { if y & 1 > 0 { ret = ret * cur % modulo; } cur = cur * cur % modulo; y >>= 1; } ret } 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 &v in euler.iter().skip(1).rev() { size[par[v].unwrap()] += size[v]; } (dist, par, size, euler) } // ------------ Kruskal's algorithm start ------------ pub fn kruskal(graph: &mut UndirectedGraph, edges: &mut [(usize, usize, C)]) -> Vec<(usize, usize, C)> { edges.sort_by_key(|x| x.2); let mut res = Vec::with_capacity(graph.size() - 1); let mut uf = UnionFind::new(graph.size()); for &e in edges.iter() { if uf.unite(e.0, e.1).is_ok() { graph.add_edge(e.0, e.1, e.2); res.push(e); } } res } // ------------ Kruskal's algorithm end ------------ // ------------ UnionFind start ------------ #[derive(Clone, Debug)] pub struct UnionFind(Vec); impl UnionFind { pub fn new(len: usize) -> Self { Self(vec![-1; len]) } pub fn find(&mut self, i: usize) -> usize { self._climb(i).0 } pub fn size(&mut self, i: usize) -> usize { self._climb(i).1 } pub fn unite(&mut self, u: usize, v: usize) -> Result<(), ()> { let (mut u, su) = self._climb(u); let (mut v, sv) = self._climb(v); if u == v { return Err(()); } if su < sv { std::mem::swap(&mut u, &mut v); } self.0[u] += self.0[v]; self.0[v] = u as isize; Ok(()) } pub fn is_same(&mut self, u: usize, v:usize) -> bool { self.find(u) == self.find(v) } fn _climb(&mut self, i: usize) -> (usize, usize) { assert!(i < self.0.len()); let mut v = i; while self.0[v] >= 0 { let p = self.0[v] as usize; if self.0[p] >= 0 { self.0[v] = self.0[p]; v = self.0[p] as usize; } else { v = p; } } (v, -self.0[v] as usize) } } // ------------ UnionFind end ------------ // TODO: verify // ------------ Potentialized UnionFind start ------------ #[derive(Clone, Debug)] pub struct PotentializedUnionFind{ data: Vec, ws: Vec } impl PotentializedUnionFind { pub fn new(len: usize) -> Self { Self{ data: vec![-1; len], ws: vec![T::zero(); len] } } pub fn find(&mut self, i: usize) -> usize { self._climb(i).0 } pub fn size(&mut self, i: usize) -> usize { self._climb(i).1 } pub fn potential(&mut self, i: usize) -> T { self._climb(i).2 } /// potential[v] - potential[u] = w /// keep potential[u] unchanged pub fn unite(&mut self, u: usize, v: usize, mut w: T) -> Result<(), ()> { let (u, su, wu) = self._climb(u); let (v, sv, wv) = self._climb(v); if u == v { return if w == -wu + wv { Ok(()) } else { Err(()) }; } w = -self.ws[u].clone() + wu + w + self.ws[v].clone() + -wv; if su < sv { self.data[v] += self.data[u]; self.data[u] = v as isize; self.ws[v] = self.ws[u].clone() + w.clone(); self.ws[u] = -w.clone(); } else { self.data[u] += self.data[v]; self.data[v] = u as isize; self.ws[v] = w.clone(); } Ok(()) } pub fn is_same(&mut self, u: usize, v:usize) -> bool { self.find(u) == self.find(v) } /// potential[v] - potential[u] pub fn diff(&mut self, u: usize, v: usize) -> Option { let (u, _, wu) = self._climb(u); let (v, _, wv) = self._climb(v); if u == v { Some(-wu + wv) } else { None } } pub fn weigh(&mut self, u: usize, w: T) { let p = self.find(u); self.ws[p] = self.ws[p].clone() + w; } /// _climb(i) -> (root, group size, potential) fn _climb(&mut self, i: usize) -> (usize, usize, T) { assert!(i < self.data.len()); let mut v = i; let mut w = T::zero(); while self.data[v] >= 0 { w = self.ws[v].clone() + w; let p = self.data[v] as usize; if self.data[p] >= 0 { self.data[v] = self.data[p]; self.ws[v] = self.ws[p].clone() + self.ws[v].clone(); } v = p; } w = self.ws[v].clone() + w; (v, -self.data[v] as usize, w) } } // ------------ Potentialized UnionFind end ------------ // TODO: verify // ------------ Iterative UnionFind start ------------ #[derive(Clone, Debug)] pub struct IterativeUnionFind(Vec, Vec); impl IterativeUnionFind { pub fn new(len: usize) -> Self { Self(vec![-1; len], (0..len).collect()) } pub fn find(&mut self, i: usize) -> usize { self._climb(i).0 } pub fn size(&mut self, i: usize) -> usize { self._climb(i).1 } pub fn unite(&mut self, u: usize, v: usize) -> Result<(), ()> { let (mut u, su) = self._climb(u); let (mut v, sv) = self._climb(v); if u == v { return Err(()); } if su < sv { std::mem::swap(&mut u, &mut v); } self.0[u] += self.0[v]; self.0[v] = u as isize; self.1.swap(u, v); Ok(()) } pub fn is_same(&mut self, u: usize, v:usize) -> bool { self.find(u) == self.find(v) } pub fn iter_group(&mut self, u: usize) -> Vec { let mut res = Vec::with_capacity(self.size(u)); res.push(u); let mut v = self.1[u]; while v != u { res.push(v); v = self.1[v]; } res } fn _climb(&mut self, i: usize) -> (usize, usize) { assert!(i < self.0.len()); let mut v = i; while self.0[v] >= 0 { let p = self.0[v] as usize; if self.0[p] >= 0 { self.0[v] = self.0[p]; v = self.0[p] as usize; } else { v = p; } } (v, -self.0[v] as usize) } } // ------------ Iterative UnionFind 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 ------------ // ------------ 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 ------------ // ------------ 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() } pub fn scan(&mut self) -> ::Output { ::scan(self) } pub fn scan_vec(&mut self, n: usize) -> Vec<::Output> { (0..n).map(|_| self.scan::()).collect() } pub fn print(&mut self, x: 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 { type Output; fn scan(io: &mut IO) -> Self::Output; } macro_rules! impl_scan { ($($t:tt),*) => { $( impl Scan for $t { type Output = Self; fn scan(s: &mut IO) -> Self::Output { s.scan_str().parse().unwrap() } } )* }; } impl_scan!(i16, i32, i64, isize, u16, u32, u64, usize, String, f32, f64); impl Scan for char { type Output = char; fn scan(s: &mut IO) -> Self::Output { s.scan_str().chars().next().unwrap() } } pub enum Bytes {} impl Scan for Bytes { type Output = &'static [u8]; fn scan(s: &mut IO) -> Self::Output { s.scan_str().as_bytes() } } pub enum Chars {} impl Scan for Chars { type Output = Vec; fn scan(s: &mut IO) -> Self::Output { s.scan_str().chars().collect() } } pub enum Usize1 {} impl Scan for Usize1 { type Output = usize; fn scan(s: &mut IO) -> Self::Output { s.scan::().wrapping_sub(1) } } impl Scan for (T, U) { type Output = (T::Output, U::Output); fn scan(s: &mut IO) -> Self::Output { (T::scan(s), U::scan(s)) } } impl Scan for (T, U, V) { type Output = (T::Output, U::Output, V::Output); fn scan(s: &mut IO) -> Self::Output { (T::scan(s), U::scan(s), V::scan(s)) } } impl Scan for (T, U, V, W) { type Output = (T::Output, U::Output, V::Output, W::Output); fn scan(s: &mut IO) -> Self::Output { (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, f32, f64); 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 String { 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); } } mod neboccoio_macro { #[macro_export] macro_rules! input { (@start $io:tt @read @rest) => {}; (@start $io:tt @read @rest, $($rest: tt)*) => { input!(@start $io @read @rest $($rest)*) }; (@start $io:tt @read @rest mut $($rest:tt)*) => { input!(@start $io @read @mut [mut] @rest $($rest)*) }; (@start $io:tt @read @rest $($rest:tt)*) => { input!(@start $io @read @mut [] @rest $($rest)*) }; (@start $io:tt @read @mut [$($mut:tt)?] @rest $var:tt: [[$kind:tt; $len1:expr]; $len2:expr] $($rest:tt)*) => { let $($mut)* $var = (0..$len2).map(|_| $io.scan_vec::<$kind>($len1)).collect::>>(); input!(@start $io @read @rest $($rest)*) }; (@start $io:tt @read @mut [$($mut:tt)?] @rest $var:tt: [$kind:tt; $len:expr] $($rest:tt)*) => { let $($mut)* $var = $io.scan_vec::<$kind>($len); input!(@start $io @read @rest $($rest)*) }; (@start $io:tt @read @mut [$($mut:tt)?] @rest $var:tt: $kind:tt $($rest:tt)*) => { let $($mut)* $var = $io.scan::<$kind>(); input!(@start $io @read @rest $($rest)*) }; (from $io:tt $($rest:tt)*) => { input!(@start $io @read @rest $($rest)*) }; } } // ------------ io module end ------------