import scala.collection.mutable.* import scala.io.StdIn.* import scala.util.chaining.* import scala.math.* import scala.reflect.ClassTag import scala.util.* import scala.annotation.tailrec import scala.collection.mutable extension (value: Int) inline def isSet(digit: Int): Boolean = ((value >> digit) & 1) != 0 @main def main = inline val MOD = 1000000007 val n = readLine.toInt val edges = Array.fill(n - 1){ val Array(a, b, c) = readLine.split(' ').map(_.toInt) (a - 1, b - 1, c) } val graph = Array.fill(n){ArrayBuffer[(Int, Int)]()} for (a, b, c) <- edges do graph(a).addOne((b, c)) graph(b).addOne((a, c)) val depth = Array.fill(n){-1}.tap(_(0) = 0) val queue = Queue(0) while queue.nonEmpty do val top = queue.dequeue() for (next, _) <- graph(top) if depth(next) == -1 do depth(next) = depth(top) + 1 queue.enqueue(next) val fromLeaf = (0 until n).sortBy(depth)(using Ordering[Int].reverse).toArray val endPath = Array.fill(n){0} var result = 0L for d <- 0 until 30 do java.util.Arrays.fill(endPath, 0) var onePath = 0L for node <- fromLeaf do var count = 0 for (child, c) <- graph(node) if depth(child) > depth(node) && c.isSet(d) do onePath += (count + 1L) * (endPath(child) + 1L) % MOD count += endPath(child) + 1 endPath(node) = count result += (onePath % MOD << d) % MOD println(result % MOD)