MOD = 10**9+7 N = int(input()) G = [list() for _ in range(N + 1)] for i in range(N - 1): u, v, w = map(int, input().split()) G[u].append((v, w)) G[v].append((u, w)) limit = 30 #limit = 3 DP = [[0] * (limit) for _ in range(N + 1)] # 1根付き木で解く par = [-1] * (N + 1) weight = [-1] * (N + 1) stack = [~1, 1] while stack: pos = stack.pop() if pos > 0: # 行きがけ # 子どもをstackに詰める oya = par[pos] for nex, w in G[pos]: if nex == oya: continue par[nex] = pos weight[nex] = w stack.append(~nex) stack.append(nex) else: if par[~pos] == -1: continue # 帰りがけ # 親に計上 w = weight[~pos] oya = par[~pos] for i in range(limit): if (w >> i) & 1 == 1: DP[oya][i] += DP[~pos][i] + 1 DP[oya][i] %= MOD #print(DP) # 全方位木DP stack = [~1, 1] cnt = [0] * limit while stack: pos = stack.pop() if pos > 0: # 行きがけ # DPの調整 oya = par[pos] # 根の移動に伴う調整 if pos != 1: w = weight[pos] weight[pos] = -1 weight[oya] = w for i in range(limit): if (w >> i) & 1 == 1: DP[oya][i] -= DP[pos][i] + 1 DP[pos][i] += DP[oya][i] + 1 # 更新後のDP[pos] を追加する # 答えを出す for i in range(limit): cnt[i] += DP[pos][i] cnt[i] %= MOD for nex, w in G[pos]: if nex == oya: continue stack.append(~nex) stack.append(nex) else: if par[~pos] == -1: continue # 帰りがけ oya = par[~pos] # 戻し先 # weight 戻し w = weight[oya] weight[~pos] = w weight[oya] = -1 # DP戻し for i in range(limit): if (w >> i) & 1 == 1: # ~pos から oya(戻し先)の寄与を削る DP[~pos][i] -= DP[oya][i] + 1 DP[oya][i] += DP[~pos][i] + 1 #print(DP) #print(cnt) ans = 0 for i in range(limit): ans += (1<