main = -> { N = gets.to_i edges = Array.new(N - 1) { a, b, c = gets.split.map(&:to_i); [a - 1, b - 1, c] } fact = Factorial.new(N, MOD) comb = (0 .. N).map { |c| fact.comb(c, 2) } ans = 0 (0 .. 30).each do |bit| uf = UnionFind.new(N) edges.each do |a, b, c| uf.merge(a, b) if c[bit] == 1 end leaders = (0 ... N).map { uf.leader(_1) }.uniq ans += leaders.sum { |i| comb[uf.size(i)] } * 2.pow(bit, MOD) ans %= MOD end puts ans } MOD = 10**9 + 7 class Factorial def initialize(max, mod) @mod = mod @fac = [1, 1] @fin = [1, 1] @inv = [nil, 1] (2 .. max).each do |i| @fac[i] = @fac[i - 1] * i % mod @inv[i] = mod - @inv[mod % i] * (mod / i) % mod @fin[i] = @fin[i - 1] * @inv[i] % mod end end def fact(n) @fac[n] end def comb(n, k) return 0 if n < k or n < 0 or k < 0 @fac[n] * @fin[k] % @mod * @fin[n - k] % @mod end end class UnionFind def initialize(size); @p = Array.new(size, -1); end def leader(i); j = i; j, i = i, @p[j] = @p[i] until @p[i] < 0; i; end def merge(i, j); k, l = leader(i), leader(j); return false if k == l; k, l = l, k if @p[k] > @p[l]; @p[k] += @p[l]; @p[l] = k; true; end def same?(i, j); leader(i) == leader(j); end def size(i); -@p[leader(i)]; end end main.call