Kundu is true tree lover. Tree is a connected graph having N vertices and N-1  edges. Today when he got a tree, he colored each edge with one of either red(r) or black(b) color. He is interested in knowing how many triplets(a,b,c) of vertices are there , such that, there is atleast one edge having red color on all the three paths i.e. from vertex a to b, vertex b to c and vertex c to a . Note that (a,b,c), (b,a,c) and all such permutations will be considered as the same triplet. 

If the answer is greater than $10^{9}$ + 7, print the answer modulo (%) $10^{9}$ + 7.

Input Format 

The first line contains an integer N, i.e., the number of vertices in tree. 

The next N-1 lines represent edges:  2 space separated integers denoting an edge followed by a color of the edge. A color of an edge is denoted by a small letter of English alphabet, and it can be either red(r) or black(b).  

Output Format 

Print a single number i.e. the number of triplets.  

Constraints 

1 ≤ N ≤ $10^{5}$
 
A node is numbered between 1 to N.  

Sample Input  

5
1 2 b
2 3 r
3 4 r
4 5 b

Sample Output  

4

Explanation

Given tree is something like this.

(2,3,4) is one such triplet because on all paths i.e 2 to 3, 3 to 4 and 2 to 4 there is atleast one edge having red color.

(2,3,5), (1,3,4) and (1,3,5) are other such triplets. 

Note that (1,2,3) is NOT a triplet, because the path from 1 to 2 does not have an edge with red color.

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Spanning trees


Solutions:
n = int(input())
p = list(range(n))
rank = [0] * n
size = [1] * n

def get(v):
	stack = []
	while p[v] != v:
		stack.append(v)
		v = p[v]
	for u in stack:
		p[u] = v
	return v

def union(v1, v2):
	v1 = get(v1)
	v2 = get(v2)
	if v1 == v2:
		return
	if rank[v1] < rank[v2]:
		(v1, v2) = (v2, v1)
	size[v1] += size[v2]
	p[v2] = v1
	rank[v1] += 1
for _ in range(n - 1):
	(x, y, col) = input().split()
	if col == 'b':
		union(int(x) - 1, int(y) - 1)
a = [size[i] for i in range(n) if p[i] == i]
MOD = 10 ** 9 + 7

def solve(a):
	s1 = [0]
	for x in a:
		s1.append((s1[-1] + x) % MOD)
	s2 = [0]
	for (i, x) in enumerate(a):
		s2.append((s2[-1] + x * s1[i]) % MOD)
	s3 = [0]
	for (i, x) in enumerate(a):
		s3.append((s3[-1] + x * s2[i]) % MOD)
	return s3[-1]
print(solve(a))


MOD = 10 ** 9 + 7
MOD_INV_6 = 166666668
N = int(input())
leader = list(range(N))
for i in range(N - 1):
	(a, b, c) = input().split()
	a = int(a) - 1
	b = int(b) - 1
	if c == 'b':
		p = a
		while p != leader[p]:
			p = leader[p]
		p2 = b
		while p2 != leader[p2]:
			p2 = leader[p2]
		leader[p2] = p
counts = [0] * N
for i in range(N):
	p = leader[i]
	while p != leader[p]:
		p = leader[p]
	counts[p] += 1
total_1 = 0
total_2 = 0
total_3 = 0
for i in range(N):
	total_1 += counts[i]
	total_2 += counts[i] * counts[i]
	total_3 += counts[i] * counts[i] * counts[i]
	total_1 %= MOD
	total_2 %= MOD
	total_3 %= MOD
total = total_1 * total_1 * total_1 % MOD
total -= 3 * total_2 * total_1
total %= MOD
total += 2 * total_3
total %= MOD
total *= MOD_INV_6
total %= MOD
if total < 0:
	total += MOD
print(total)


MOD = 10 ** 9 + 7
N = int(input())
tree = [[] for _ in range(N)]
for _ in range(N - 1):
	(a, b, c) = input().split()
	if c == 'b':
		(a, b) = (int(a) - 1, int(b) - 1)
		tree[a].append(b)
		tree[b].append(a)
marked = [False] * N
groups = {}
for i in range(N):
	if marked[i]:
		continue
	(count, stack) = (0, [i])
	while stack:
		n = stack.pop()
		if marked[n]:
			continue
		count += 1
		marked[n] = True
		for v in tree[n]:
			stack.append(v)
	groups[count] = groups.get(count, 0) + 1
indexes = sorted(groups)
total1 = 0
for i in range(len(indexes)):
	a = groups[indexes[i]]
	if a >= 3:
		total1 += a * (a - 1) * (a - 2) // 6 * indexes[i] ** 3
total2 = 0
for i in range(len(indexes)):
	for j in range(len(indexes)):
		if i == j:
			continue
		a = groups[indexes[i]]
		b = groups[indexes[j]]
		if a >= 2:
			total2 += a * (a - 1) // 2 * b * indexes[i] ** 2 * indexes[j]
total3 = 0
for i in range(len(indexes)):
	for j in range(i):
		for k in range(j):
			a = groups[indexes[i]]
			b = groups[indexes[j]]
			c = groups[indexes[k]]
			total3 += a * b * c * indexes[i] * indexes[j] * indexes[k]
print((total1 + total2 + total3) % MOD)


import collections, sys
MOD = 1000000007

def connected_components(lists):
	neighbors = collections.defaultdict(set)
	seen = set()
	for each in lists:
		for item in each:
			neighbors[item].update(each)

	def component(node, neighbors=neighbors, seen=seen, see=seen.add):
		nodes = set([node])
		next_node = nodes.pop
		while nodes:
			node = next_node()
			see(node)
			nodes |= neighbors[node] - seen
			yield node
	for node in neighbors:
		if node not in seen:
			yield sorted(component(node))
N = int(sys.stdin.readline())
if N < 3:
	print(0)
else:
	edges = []
	for _ in range(N - 1):
		line = sys.stdin.readline().strip()
		if line.endswith('b'):
			edges.append(list(map(int, line[:-2].split())))
	subtrees = connected_components(edges)
	invalid = sum((len(t) * (len(t) - 1) * (3 * N - 2 * len(t) - 2) // 6 for t in subtrees))
	total = N * (N - 1) * (N - 2) // 6
	print((total - invalid) % MOD)


import collections, sys
MOD = 1000000007

def connected_components(lists):
	neighbors = collections.defaultdict(set)
	seen = set()
	for each in lists:
		for item in each:
			neighbors[item].update(each)

	def component(node, neighbors=neighbors, seen=seen, see=seen.add):
		nodes = set([node])
		next_node = nodes.pop
		while nodes:
			node = next_node()
			see(node)
			nodes |= neighbors[node] - seen
			yield node
	for node in neighbors:
		if node not in seen:
			yield sorted(component(node))
N = int(sys.stdin.readline())
if N < 3:
	print(0)
else:
	edges = []
	for _ in range(N - 1):
		line = sys.stdin.readline().strip()
		if line.endswith('b'):
			edges.append(list(map(int, line[:-2].split())))
	subtrees = connected_components(edges)
	invalid = sum((len(t) * (len(t) - 1) * (3 * N - 2 * len(t) - 2) // 6 for t in subtrees))
	total = N * (N - 1) * (N - 2) // 6
	print((total - invalid) % MOD)


import collections, sys
MOD = 1000000007

def connected_components(lists):
	neighbors = collections.defaultdict(set)
	seen = set()
	for each in lists:
		for item in each:
			neighbors[item].update(each)

	def component(node, neighbors=neighbors, seen=seen, see=seen.add):
		nodes = set([node])
		next_node = nodes.pop
		while nodes:
			node = next_node()
			see(node)
			nodes |= neighbors[node] - seen
			yield node
	for node in neighbors:
		if node not in seen:
			yield sorted(component(node))
N = int(sys.stdin.readline())
if N < 3:
	print(0)
else:
	edges = []
	for _ in range(N - 1):
		line = sys.stdin.readline().strip()
		if line.endswith('b'):
			edges.append(list(map(int, line[:-2].split())))
	subtrees = connected_components(edges)
	invalid = sum((len(t) * (len(t) - 1) * (3 * N - 2 * len(t) - 2) // 6 for t in subtrees))
	total = N * (N - 1) * (N - 2) // 6
	print((total - invalid) % MOD)


import collections, sys
MOD = 1000000007

def connected_components(lists):
	neighbors = collections.defaultdict(set)
	seen = set()
	for each in lists:
		for item in each:
			neighbors[item].update(each)

	def component(node, neighbors=neighbors, seen=seen, see=seen.add):
		nodes = set([node])
		next_node = nodes.pop
		while nodes:
			node = next_node()
			see(node)
			nodes |= neighbors[node] - seen
			yield node
	for node in neighbors:
		if node not in seen:
			yield sorted(component(node))
N = int(sys.stdin.readline())
if N < 3:
	print(0)
else:
	edges = []
	for _ in range(N - 1):
		line = sys.stdin.readline().strip()
		if line.endswith('b'):
			edges.append(list(map(int, line[:-2].split())))
	subtrees = connected_components(edges)
	invalid = sum((len(t) * (len(t) - 1) * (3 * N - 2 * len(t) - 2) // 6 for t in subtrees))
	total = N * (N - 1) * (N - 2) // 6
	print((total - invalid) % MOD)


import collections, sys
MOD = 1000000007

def connected_components(lists):
	neighbors = collections.defaultdict(set)
	seen = set()
	for each in lists:
		for item in each:
			neighbors[item].update(each)

	def component(node, neighbors=neighbors, seen=seen, see=seen.add):
		nodes = set([node])
		next_node = nodes.pop
		while nodes:
			node = next_node()
			see(node)
			nodes |= neighbors[node] - seen
			yield node
	for node in neighbors:
		if node not in seen:
			yield sorted(component(node))
N = int(sys.stdin.readline())
if N < 3:
	print(0)
else:
	edges = []
	for _ in range(N - 1):
		line = sys.stdin.readline().strip()
		if line.endswith('b'):
			edges.append(list(map(int, line[:-2].split())))
	subtrees = connected_components(edges)
	invalid = sum((len(t) * (len(t) - 1) * (3 * N - 2 * len(t) - 2) // 6 for t in subtrees))
	total = N * (N - 1) * (N - 2) // 6
	print((total - invalid) % MOD)


import collections, sys
MOD = 1000000007

def connected_components(lists):
	neighbors = collections.defaultdict(set)
	seen = set()
	for each in lists:
		for item in each:
			neighbors[item].update(each)

	def component(node, neighbors=neighbors, seen=seen, see=seen.add):
		nodes = set([node])
		next_node = nodes.pop
		while nodes:
			node = next_node()
			see(node)
			nodes |= neighbors[node] - seen
			yield node
	for node in neighbors:
		if node not in seen:
			yield sorted(component(node))
N = int(sys.stdin.readline())
if N < 3:
	print(0)
else:
	edges = []
	for _ in range(N - 1):
		line = sys.stdin.readline().strip()
		if line.endswith('b'):
			edges.append(list(map(int, line[:-2].split())))
	subtrees = connected_components(edges)
	invalid = sum((len(t) * (len(t) - 1) * (3 * N - 2 * len(t) - 2) // 6 for t in subtrees))
	total = N * (N - 1) * (N - 2) // 6
	print((total - invalid) % MOD)


M = 10 ** 9 + 7

class ParentPointerTree(object):

	def __init__(self):
		self.parent = self
		self.size = 1

	def find(self):
		p = self
		while p != p.parent:
			p = p.parent
		self.parent = p
		return p

	def union(self, other):
		(self_root, other_root) = (self.find(), other.find())
		if self_root != other_root:
			if self_root.size < other_root.size:
				self_root.parent = other_root
				other_root.size += self_root.size
			else:
				other_root.parent = self_root
				self_root.size += other_root.size
n = int(input())
nodes = {k: ParentPointerTree() for k in range(1, n + 1)}
for _ in range(n - 1):
	(n1, n2, colour) = input().split()
	(n1, n2) = (int(n1), int(n2))
	if colour == 'b':
		nodes[n1].union(nodes[n2])
roots = list(set((t.find() for t in nodes.values())))
all_triples = n % M * (max(n - 1, 0) % M) * (max(n - 2, 0) % M) // 6 % M
b2 = b3 = 0
for root in roots:
	m = root.size
	b3 = (b3 % M + m % M * (max(m - 1, 0) % M) * (max(m - 2, 0) % M) // 6 % M) % M
	b2 = (b2 % M + m % M * (max(m - 1, 0) % M) * ((n - m) % M) // 2 % M) % M
print((all_triples % M - b3 % M - b2 % M) % M)


class Graph:

	def __init__(self, n):
		self.data = [[] for i in range(n)]

	def add_edge(self, v, w):
		self.data[v].append(w)

	def adj(self, v):
		return self.data[v]
n = int(input())
g = Graph(n)
for i in range(n - 1):
	e = input().strip().split(' ')
	if e[2] == 'b':
		v = int(e[0]) - 1
		w = int(e[1]) - 1
		g.add_edge(v, w)
		g.add_edge(w, v)
marked = [0] * n

def dfs(group, n):
	marked[n] = 1
	group.add(n)
	for i in g.adj(n):
		if not marked[i]:
			dfs(group, i)
groups = []
for i in range(n):
	if not marked[i]:
		group = set()
		dfs(group, i)
		groups.append(group)

def count_it(group):
	return len(group)
counts = list(map(count_it, groups))
l = len(counts)
state = [[0] * 3 for i in range(l)]
state[0][0] = counts[0]
for i in range(1, l):
	for j in range(3):
		if i < j:
			continue
		state[i][j] = state[i - 1][j] + counts[i] * (state[i - 1][j - 1] if j >= 1 else 1)
print(state[-1][-1] % (10 ** 9 + 7))


import math

class Node:

	def __init__(self, name):
		self.parent = None
		self.name = name
		self.size = 1

	def get_leader(self):
		if self.parent is None:
			return self
		self.parent = self.parent.get_leader()
		return self.parent

	def union(self, other):
		my_leader = self.get_leader()
		other_leader = other.get_leader()
		if my_leader is other_leader:
			return
		if other_leader.size > my_leader.size:
			my_leader.parent = other_leader
			other_leader.size += my_leader.size
		else:
			other_leader.parent = my_leader
			my_leader.size += other_leader.size

def n_choose_k(n, k):
	if n < k:
		return 0
	m = 1
	for i in range(0, k):
		m *= n - i
	m /= math.factorial(k)
	return m
number_of_node = int(input().strip())
count = n_choose_k(number_of_node, 3)
max_count = pow(10, 9) + 7
nodes = {}
blued = set()
for i in range(0, number_of_node):
	nodes[i + 1] = Node(i + 1)
for i in range(1, number_of_node):
	line = input().strip().split(' ')
	node1 = nodes[int(line[0])]
	node2 = nodes[int(line[1])]
	color = line[2]
	if color is 'b':
		node1.union(node2)
		blued.add(node1)
		blued.add(node2)
clusters = {}
while len(blued) > 0:
	node = blued.pop()
	node_leader = node.get_leader()
	clusters[node_leader.name] = node_leader.size
for key in clusters:
	if clusters[key] < 2:
		continue
	count -= n_choose_k(clusters[key], 3)
	count -= n_choose_k(clusters[key], 2) * (number_of_node - clusters[key])
print(int(count) % max_count)


import collections, sys
MOD = 1000000007

def connected_components(lists):
	neighbors = collections.defaultdict(set)
	seen = set()
	for each in lists:
		for item in each:
			neighbors[item].update(each)

	def component(node, neighbors=neighbors, seen=seen, see=seen.add):
		nodes = set([node])
		next_node = nodes.pop
		while nodes:
			node = next_node()
			see(node)
			nodes |= neighbors[node] - seen
			yield node
	for node in neighbors:
		if node not in seen:
			yield sorted(component(node))
N = int(sys.stdin.readline())
if N < 3:
	print(0)
else:
	edges = []
	for _ in range(N - 1):
		line = sys.stdin.readline().strip()
		if line.endswith('b'):
			edges.append(list(map(int, line[:-2].split())))
	subtrees = connected_components(edges)
	invalid = sum((len(t) * (len(t) - 1) * (3 * N - 2 * len(t) - 2) // 6 for t in subtrees))
	total = N * (N - 1) * (N - 2) // 6
	print((total - invalid) % MOD)


MOD = 10 ** 9 + 7

def join(who1, who2, parent, pop):
	who1 = flatten(who1, parent, pop)
	who2 = flatten(who2, parent, pop)
	if who1 == who2:
		return
	if who1 > who2:
		(who1, who2) = (who2, who1)
	parent[who2] = who1
	pop[who1] += pop[who2]

def flatten(who, parent, pop):
	start = who
	li = [who]
	while parent[who] is not None:
		who = parent[who]
		li.append(who)
	ans = who
	for (who, dad) in zip(li[:-2], li[1:]):
		pop[dad] -= pop[who]
		parent[who] = ans
	return ans
n = int(input())
parent = [None] * n
pop = [1] * n
for _ in range(1, n):
	edge = input().split()
	assert len(edge) == 3
	if edge[-1] == 'b':
		join(int(edge[0]) - 1, int(edge[1]) - 1, parent, pop)
compsize = [pop1 for (pop1, par1) in zip(pop, parent) if par1 is None]
singles = pairs = trips = 0
for size in compsize:
	trips += size * pairs
	pairs += size * singles
	singles += size
print(trips % MOD)


class Node(object):

	def __init__(self, idx, count=1, parent=None):
		self.idx = idx
		self.count = count
		self.parent = parent

	def root(self):
		r = self
		while r.parent:
			r = r.parent
		return r

def merge(rootlist, a, b):
	ra = a.root()
	rb = b.root()
	if ra == rb:
		return
	if ra.count < rb.count:
		ra.parent = rb
		rb.count += ra.count
		i = ra.idx
	else:
		rb.parent = ra
		ra.count += rb.count
		i = rb.idx
	rootlist[i] = rootlist[-1]
	rootlist[i].idx = i
	rootlist.pop()
n = int(input())
rootlist = [Node(i) for i in range(n + 1)]
nodelist = rootlist[:]
for _ in range(n - 1):
	(i, j, c) = input().split()
	if c == 'b':
		merge(rootlist, nodelist[int(i)], nodelist[int(j)])
print((n * (n - 1) * (n - 2) - sum((r.count * (r.count - 1) * (3 * n - 2 * r.count - 2) for r in rootlist))) // 6 % (10 ** 9 + 7))


N = int(input().strip())
reds = [set() for i in range(N + 1)]
blacks = [set() for i in range(N + 1)]
for i in range(N - 1):
	(v1, v2, color) = input().strip().split()
	v1 = int(v1)
	v2 = int(v2)
	temp = set([v1, v2])
	if color == 'b':
		ss = blacks
	else:
		ss = reds
	ss[v1].add(v2)
	ss[v2].add(v1)
black_sets = []
idx = 1
visited = set()
while idx <= N:
	while idx <= N and idx in visited:
		idx += 1
	if idx > N:
		break
	curr = set([idx])
	q = blacks[idx]
	while q:
		newQ = set()
		curr |= q
		for one in q - visited:
			newQ |= blacks[one]
		visited |= q
		q = newQ
	if len(curr) > 1:
		black_sets.append(curr)
	idx += 1
cnt_black_set = [len(_) for _ in black_sets]
cnt_black = sum(cnt_black_set)
cnt_red = N - cnt_black
res = 0
import math

def nCr(n, r):
	f = math.factorial
	res = 1
	for i in range(r):
		res *= n
		n -= 1
	return res / f(r)
for bs in black_sets:
	l = len(bs)
	temp = 0
	if l >= 2:
		temp += nCr(l, 2) * (N - l)
	if l >= 3:
		temp += nCr(l, 3)
	res += temp
res = nCr(N, 3) - res
print(int(res % (10 ** 9 + 7)))


class DisjointSet:

	def __init__(self):
		self.parent = self
		self.rank = 0
		self.count = 1

	def find(self):
		if self.parent != self:
			self.parent = self.parent.find()
		return self.parent

def union(s1, s2):
	(root1, root2) = (s1.find(), s2.find())
	if root1 == root2:
		return
	if root1.rank < root2.rank:
		root1.parent = root2
		root2.count += root1.count
	elif root1.rank > root2.rank:
		root2.parent = root1
		root1.count += root2.count
	else:
		root2.parent = root1
		root1.count += root2.count
		root1.rank += 1
N = int(input())
dsets = [DisjointSet() for i in range(N)]
for i in range(N - 1):
	(a, b, color) = tuple(input().split())
	(a, b) = (int(a) - 1, int(b) - 1)
	if color == 'b':
		union(dsets[a], dsets[b])
clusters = set([dset.find() for dset in dsets])
totcount = 0
for c in clusters:
	totcount += c.count * (c.count - 1) * (c.count - 2) / 6 + c.count * (c.count - 1) / 2 * (N - c.count)
result = (N * (N - 1) * (N - 2) / 6 - totcount) % (10 ** 9 + 7)
print(int(result))


def find(x):
	if p[x] != x:
		p[x] = find(p[x])
	return p[x]

def merge(x, y):
	x = find(x)
	y = find(y)
	if x != y:
		if c[x] > c[y]:
			p[y] = x
			c[x] += c[y]
		else:
			p[x] = y
			c[y] += c[x]
n = int(input())
p = list(range(n))
c = [1] * n
for _ in range(n - 1):
	s = input().split()
	if s[2] == 'b':
		u = int(s[0]) - 1
		v = int(s[1]) - 1
		merge(u, v)
q = set()
for x in range(n):
	q.add(find(x))
r = n * (n - 1) * (n - 2) // 6
for x in q:
	r -= (n - c[x]) * c[x] * (c[x] - 1) // 2 + c[x] * (c[x] - 1) * (c[x] - 2) // 6
print(r % (10 ** 9 + 7))


import collections, sys
MOD = 1000000007

def connected_components(lists):
	neighbors = collections.defaultdict(set)
	seen = set()
	for each in lists:
		for item in each:
			neighbors[item].update(each)

	def component(node, neighbors=neighbors, seen=seen, see=seen.add):
		nodes = set([node])
		next_node = nodes.pop
		while nodes:
			node = next_node()
			see(node)
			nodes |= neighbors[node] - seen
			yield node
	for node in neighbors:
		if node not in seen:
			yield sorted(component(node))
N = int(sys.stdin.readline())
if N < 3:
	print(0)
else:
	edges = []
	for _ in range(N - 1):
		line = sys.stdin.readline().strip()
		if line.endswith('b'):
			edges.append(list(map(int, line[:-2].split())))
	subtrees = connected_components(edges)
	invalid = sum((len(t) * (len(t) - 1) * (3 * N - 2 * len(t) - 2) // 6 for t in subtrees))
	total = N * (N - 1) * (N - 2) // 6
	print((total - invalid) % MOD)


import collections, sys
MOD = 1000000007

def connected_components(lists):
	neighbors = collections.defaultdict(set)
	seen = set()
	for each in lists:
		for item in each:
			neighbors[item].update(each)

	def component(node, neighbors=neighbors, seen=seen, see=seen.add):
		nodes = set([node])
		next_node = nodes.pop
		while nodes:
			node = next_node()
			see(node)
			nodes |= neighbors[node] - seen
			yield node
	for node in neighbors:
		if node not in seen:
			yield sorted(component(node))
N = int(input())
if N < 3:
	print(0)
else:
	edges = []
	for _ in range(N - 1):
		line = input().strip()
		if line.endswith('b'):
			edges.append(list(map(int, line[:-2].split())))
	subtrees = connected_components(edges)
	invalid = sum((len(t) * (len(t) - 1) * (3 * N - 2 * len(t) - 2) // 6 for t in subtrees))
	total = N * (N - 1) * (N - 2) // 6
	print((total - invalid) % MOD)


def Find(uf, u):
	if u != uf[u]:
		uf[u] = Find(uf, uf[u])
	return uf[u]

def Unify(uf, sz, u, v):
	label_u = Find(uf, u)
	label_v = Find(uf, v)
	if label_u != label_v:
		if sz[label_u] < sz[label_v]:
			uf[label_u] = label_v
			sz[label_v] += sz[label_u]
		else:
			uf[label_v] = label_u
			sz[label_u] += sz[label_v]
N = int(input())
uf_rd = list(range(N + 1))
sz_rd = [1] * (N + 1)
uf_bl = list(range(N + 1))
sz_bl = [1] * (N + 1)
for _ in range(N - 1):
	query = input().split()
	(u, v) = map(int, query[:2])
	color = query[-1]
	if color == 'r':
		Unify(uf_rd, sz_rd, u, v)
	else:
		Unify(uf_bl, sz_bl, u, v)
rd_components = [sz_rd[i] for i in range(1, N + 1) if uf_rd[i] == i and sz_rd[i] > 1]
bl_components = [sz_bl[i] for i in range(1, N + 1) if uf_bl[i] == i and sz_bl[i] > 1]
res = N * (N - 1) * (N - 2) // 6
for bl_comp in bl_components:
	if bl_comp > 2:
		res -= bl_comp * (bl_comp - 1) * (bl_comp - 2) // 6
	res -= (N - bl_comp) * bl_comp * (bl_comp - 1) // 2
res %= 10 ** 9 + 7
print(res)


import collections, sys
MOD = 1000000007

def connected_components(lists):
	neighbors = collections.defaultdict(set)
	seen = set()
	for each in lists:
		for item in each:
			neighbors[item].update(each)

	def component(node, neighbors=neighbors, seen=seen, see=seen.add):
		nodes = set([node])
		next_node = nodes.pop
		while nodes:
			node = next_node()
			see(node)
			nodes |= neighbors[node] - seen
			yield node
	for node in neighbors:
		if node not in seen:
			yield sorted(component(node))
N = int(sys.stdin.readline())
if N < 3:
	print(0)
else:
	edges = []
	for _ in range(N - 1):
		line = sys.stdin.readline().strip()
		if line.endswith('b'):
			edges.append(list(map(int, line[:-2].split())))
	subtrees = connected_components(edges)
	invalid = sum((len(t) * (len(t) - 1) * (3 * N - 2 * len(t) - 2) // 6 for t in subtrees))
	total = N * (N - 1) * (N - 2) // 6
	print((total - invalid) % MOD)


def find(x):
	while uf[x] >= 0:
		if uf[uf[x]] >= 0:
			uf[x] = uf[uf[x]]
		x = uf[x]
	return x
n = int(input())
uf = [-1] * n
for i in range(n - 1):
	(x, y, col) = input().split()
	if col == 'b':
		(x, y) = (find(int(x) - 1), find(int(y) - 1))
		if uf[x] > uf[y]:
			(x, y) = (y, x)
		uf[x] += uf[y]
		uf[y] = x
(a, b, c) = (0, 0, 0)
for i in range(n):
	if uf[i] < 0:
		c -= b * uf[i]
		b -= a * uf[i]
		a -= uf[i]
print(c % int(1000000000.0 + 7))


def find(x):
	while uf[x] >= 0:
		if uf[uf[x]] >= 0:
			uf[x] = uf[uf[x]]
		x = uf[x]
	return x
n = int(input())
uf = [-1] * n
for i in range(n - 1):
	(x, y, col) = input().split()
	if col == 'b':
		(x, y) = (find(int(x) - 1), find(int(y) - 1))
		if uf[x] > uf[y]:
			(x, y) = (y, x)
		uf[x] += uf[y]
		uf[y] = x
(a, b, c) = (0, 0, 0)
for i in range(n):
	if uf[i] < 0:
		c -= b * uf[i]
		b -= a * uf[i]
		a -= uf[i]
print(c % int(1000000000.0 + 7))


def find(x):
	while uf[x] >= 0:
		if uf[uf[x]] >= 0:
			uf[x] = uf[uf[x]]
		x = uf[x]
	return x
n = int(input())
uf = [-1] * n
for i in range(n - 1):
	(x, y, col) = input().split()
	if col == 'b':
		(x, y) = (find(int(x) - 1), find(int(y) - 1))
		if uf[x] > uf[y]:
			(x, y) = (y, x)
		uf[x] += uf[y]
		uf[y] = x
(a, b, c) = (0, 0, 0)
for i in range(n):
	if uf[i] < 0:
		c -= b * uf[i]
		b -= a * uf[i]
		a -= uf[i]
print(c % int(1000000000.0 + 7))


def find(x):
	while uf[x] >= 0:
		if uf[uf[x]] >= 0:
			uf[x] = uf[uf[x]]
		x = uf[x]
	return x
n = int(input())
uf = [-1] * n
for i in range(n - 1):
	(x, y, col) = input().split()
	if col == 'b':
		(x, y) = (find(int(x) - 1), find(int(y) - 1))
		if uf[x] > uf[y]:
			(x, y) = (y, x)
		uf[x] += uf[y]
		uf[y] = x
(a, b, c) = (0, 0, 0)
for i in range(n):
	if uf[i] < 0:
		c -= b * uf[i]
		b -= a * uf[i]
		a -= uf[i]
print(c % int(1000000000.0 + 7))


n = int(input())
p = list(range(n))
rank = [0] * n
size = [1] * n

def get(v):
	stack = []
	while p[v] != v:
		stack.append(v)
		v = p[v]
	for u in stack:
		p[u] = v
	return v

def union(v1, v2):
	v1 = get(v1)
	v2 = get(v2)
	if v1 == v2:
		return
	if rank[v1] < rank[v2]:
		(v1, v2) = (v2, v1)
	size[v1] += size[v2]
	p[v2] = v1
	rank[v1] += 1
for _ in range(n - 1):
	(x, y, col) = input().split()
	if col == 'b':
		union(int(x) - 1, int(y) - 1)
a = [size[i] for i in range(n) if p[i] == i]
MOD = 10 ** 9 + 7

def solve(a):
	s1 = [0]
	for x in a:
		s1.append((s1[-1] + x) % MOD)
	s2 = [0]
	for (i, x) in enumerate(a):
		s2.append((s2[-1] + x * s1[i]) % MOD)
	s3 = [0]
	for (i, x) in enumerate(a):
		s3.append((s3[-1] + x * s2[i]) % MOD)
	return s3[-1]
print(solve(a))


import collections
CAP = 10 ** 9 + 7

class DisjointSet:

	def __init__(self, n):
		self.comm = {x: x for x in range(1, n + 1)}
		self.commsz = {x: 1 for x in range(1, n + 1)}
		self.n = n

	def community(self, a):
		comm = self.comm
		updates = []
		it = a
		while it != comm.get(it, it):
			updates.append(it)
			it = comm.get(it, it)
		for node in updates:
			comm[node] = it
		return it

	def size(self, a):
		return self.commsz[self.community(a)]

	def merge(self, a, b):
		(commsz, comm) = (self.commsz, self.comm)
		(commA, commB) = (self.community(a), self.community(b))
		if commA == commB:
			return
		(big, small) = (commA, commB) if self.size(a) > self.size(b) else (commB, commA)
		comm[small] = big
		commsz[big] += commsz[small]
		commsz[small] = 0

	def sets(self):
		return {x: self.size(x) for x in self.commsz if self.commsz[x] >= 1}

def comb(n, k, arr):
	if n < k:
		return 0
	mem = collections.defaultdict(int, {(x, 0): 1 for x in range(n + 1)})
	for dk in range(1, k + 1):
		for dn in range(1, n + 1):
			mem[dn, dk] = (mem[dn - 1, dk] % CAP + mem[dn - 1, dk - 1] * arr[dn - 1] % CAP) % CAP
	return mem[n, k]
n = int(input())
dset = DisjointSet(n)
for _ in range(n - 1):
	args = input().split()
	if args[-1] == 'b':
		(a, b) = list(map(int, args[:-1]))
		dset.merge(a, b)
values = list(dset.sets().values())
print(comb(len(values), 3, values))


from math import factorial

class Node:

	def __init__(self, i):
		self.nid = i
		self.p = self
		self.rank = 0
		self.size = 1

	def union(self, other):
		xroot = self.find()
		yroot = other.find()
		if xroot == yroot:
			return
		if xroot.rank > yroot.rank:
			(xroot, yroot) = (yroot, xroot)
		xroot.p = yroot
		yroot.size += xroot.size
		if xroot.rank == yroot.rank:
			yroot.rank += 1

	def find(self):
		if self.p != self:
			self.p = self.p.find()
		return self.p

	def __str__(self):
		return '{}({}/{})'.format(self.nid, self.rank, self.size)
nodes = {}

def node(i):
	if i not in nodes:
		nodes[i] = Node(i)
	return nodes[i]

def combination(n, k):
	return factorial(n) // factorial(n - k) // factorial(k)
n = int(input().strip())
for _ in range(n - 1):
	(a, b, c) = input().strip().split(' ')
	if c == 'b':
		node(a).union(node(b))
btrees = set((ni.find() for ni in nodes.values()))
ntri = combination(n, 3)
for bt in btrees:
	if bt.size > 2:
		ntri -= combination(bt.size, 3)
	ntri -= combination(bt.size, 2) * (n - bt.size)
print(ntri % (10 ** 9 + 7))


def find(x):
	while uf[x] >= 0:
		if uf[uf[x]] >= 0:
			uf[x] = uf[uf[x]]
		x = uf[x]
	return x
n = int(input())
uf = [-1] * n
for i in range(n - 1):
	(x, y, col) = input().split()
	if col == 'b':
		(x, y) = (find(int(x) - 1), find(int(y) - 1))
		if uf[x] > uf[y]:
			(x, y) = (y, x)
		uf[x] += uf[y]
		uf[y] = x
(a, b, c) = (0, 0, 0)
for i in range(n):
	if uf[i] < 0:
		c -= b * uf[i]
		b -= a * uf[i]
		a -= uf[i]
print(c % int(1000000000.0 + 7))


class DisjointSetForest:

	def __init__(self):
		self.node_map = {}

	def make_set(self, key):
		self.node_map[key] = DisjointSetNode(key)

	def find_set(self, key):
		return self._find_set(self.node_map[key])

	def _find_set(self, x):
		if x.parent is not x:
			x.parent = self._find_set(x.parent)
		return x.parent

	def union(self, key1, key2):
		self._union(self.find_set(key1), self.find_set(key2))

	def _union(self, x, y):
		if x is y:
			return
		if x.size > y.size:
			y.parent = x
			y.parent.size += y.size
		else:
			x.parent = y
			x.parent.size += x.size

class DisjointSetNode:

	def __init__(self, key):
		self.key = key
		self.parent = self
		self.rank = 0
		self.size = 1

def triplets(n):
	return n * (n - 1) * (n - 2) // 6

def pairs(n):
	return n * (n - 1) // 2
N = int(input())
disjoint_set_forest = DisjointSetForest()
for vertex in range(1, N + 1):
	disjoint_set_forest.make_set(vertex)
for edge_index in range(N - 1):
	edge = input().split()
	colour = edge[-1]
	if colour == 'b':
		disjoint_set_forest.union(int(edge[0]), int(edge[1]))
bad_component_keys = set()
for vertex in range(1, N + 1):
	component = disjoint_set_forest.find_set(vertex)
	if component.key not in bad_component_keys:
		bad_component_keys.add(component.key)
bad_triplets = 0
for bad_component_key in bad_component_keys:
	bad_component = disjoint_set_forest.find_set(bad_component_key)
	bad_triplets += triplets(bad_component.size)
	bad_triplets += pairs(bad_component.size) * (N - bad_component.size)
	bad_triplets %= 10 ** 9 + 7
good_triplets = (triplets(N) - bad_triplets) % (10 ** 9 + 7)
print(good_triplets)


class DisjointSet:

	def __init__(self):
		self.nodes = {}
		self.num_nodes = 0

	def add_value(self, value):
		self.nodes[value] = Node()
		self.num_nodes += 1

	def _get_ult_parent(self, node):
		if node.parent is None:
			return node
		node.parent = self._get_ult_parent(node.parent)
		return node.parent

	def get_group_size(self, node_num):
		return self._get_ult_parent(self.nodes[node_num]).group_size

	def union(self, a, b):
		root_a = self._get_ult_parent(self.nodes[a])
		root_b = self._get_ult_parent(self.nodes[b])
		triangles_removed = root_a.group_size * root_b.group_size * (self.num_nodes - root_a.group_size - root_b.group_size)
		if root_a != root_b:
			if root_a.rank > root_b.rank:
				root_b.parent = root_a
				root_a.group_size += root_b.group_size
			elif root_a.rank < root_b.rank:
				root_a.parent = root_b
				root_b.group_size += root_a.group_size
			else:
				root_b.parent = root_a
				root_a.group_size += root_b.group_size
				root_a.rank += 1
		return triangles_removed

class Node:

	def __init__(self):
		self.parent = None
		self.group_size = 1
		self.rank = 0
MOD_VALUE = 10 ** 9 + 7
num_nodes = int(input())
ds = DisjointSet()
for i in range(1, num_nodes + 1):
	ds.add_value(i)
num_triangles = num_nodes * (num_nodes - 1) * (num_nodes - 2) // 6 % MOD_VALUE
for i in range(num_nodes - 1):
	(v1, v2, color) = input().split()
	if color == 'b':
		num_triangles -= ds.union(int(v1), int(v2))
		num_triangles %= MOD_VALUE
print(num_triangles)


class DisjointSet:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.total = [1] * N

	def union(self, a, b):
		a_parent = self.find(a)
		b_parent = self.find(b)
		if a_parent != b_parent:
			self.parent[b_parent] = a_parent
			self.total[a_parent] += self.total[b_parent]

	def find(self, a):
		if self.parent[a] != a:
			self.parent[a] = self.find(self.parent[a])
		return self.parent[a]

	def get_total(self, a):
		return self.total[self.find(a)]
N = int(input())
ds = DisjointSet(N)
for i in range(N - 1):
	(x, y, color) = input().split()
	if color == 'b':
		ds.union(int(x) - 1, int(y) - 1)
set_size = {ds.find(i): ds.get_total(i) for i in range(N)}
complement = sum((x * (x - 1) * (N - x) // 2 + x * (x - 1) * (x - 2) // 6 for x in set_size.values()))
print((N * (N - 1) * (N - 2) // 6 - complement) % (10 ** 9 + 7))


n = int(input())
redges = []
conns = {}

def findParent(t):
	while t != conns[t][0]:
		t = conns[t][0]
	return t
for _ in range(n - 1):
	t = input().split()
	if t[2] == 'b':
		a = int(t[0])
		b = int(t[1])
		c = a in conns
		d = b in conns
		if not c and (not d):
			conns[a] = [a, 2]
			conns[b] = [a]
		if not c and d:
			par = findParent(b)
			conns[a] = [par]
			conns[par][1] += 1
		if not d and c:
			par = findParent(a)
			conns[b] = [par]
			conns[par][1] += 1
		if c and d:
			apar = findParent(a)
			bpar = findParent(b)
			if apar != bpar:
				if conns[apar][1] > conns[bpar][1]:
					conns[apar][1] += conns[bpar][1]
					conns[bpar][0] = apar
				else:
					conns[bpar][1] += conns[apar][1]
					conns[apar][0] = bpar
	else:
		redges.append([int(t[0]), int(t[1])])
bads = 0
for i in conns:
	if conns[i][0] == i:
		cnt = conns[i][1]
		bads = bads + cnt * (cnt - 1) * (3 * n - 2 * cnt - 2) / 6
print(int(n * (n - 1) * (n - 2) / 6 - bads) % (10 ** 9 + 7))


from collections import defaultdict, Counter

def count_components(G, N):
	marks = N * [0]

	def markCC(start, mark):
		if marks[start]:
			return mark
		marks[start] = mark
		stack = [start]
		while stack:
			for e in G[stack.pop()]:
				if not marks[e]:
					marks[e] = mark
					stack.append(e)
		return mark + 1
	mark = 1
	for start in range(N):
		mark = markCC(start, mark)
	return list(Counter(marks).values())

def read_line(s):
	(c1, c2, c3) = s.split()
	return (int(c1) - 1, int(c2) - 1, c3 == 'b')
n = int(input())
graph = defaultdict(set)
for _ in range(n - 1):
	(b, e, f) = read_line(input())
	if f:
		graph[b].add(e)
		graph[e].add(b)
cc = count_components(graph, n)

def C2n(n):
	return n * (n - 1) // 2

def C3n(n):
	return n * (n - 1) * (n - 2) // 6
res = C3n(n) - sum((C2n(m) * (n - m) + C3n(m) for m in cc))
MOD = 10 ** 9 + 7
print(res % MOD)


class DisjointSet:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.total = [1] * N

	def union(self, a, b):
		a_parent = self.find(a)
		b_parent = self.find(b)
		if a_parent != b_parent:
			self.parent[b_parent] = a_parent
			self.total[a_parent] += self.total[b_parent]

	def find(self, a):
		if self.parent[a] != a:
			self.parent[a] = self.find(self.parent[a])
		return self.parent[a]

	def get_total(self, a):
		return self.total[self.find(a)]
N = int(input())
ds = DisjointSet(N)
for i in range(N - 1):
	(x, y, color) = input().split()
	if color == 'b':
		ds.union(int(x) - 1, int(y) - 1)
set_size = {ds.find(i): ds.get_total(i) for i in range(N)}
complement = sum((x * (x - 1) * (N - x) // 2 + x * (x - 1) * (x - 2) // 6 for x in set_size.values()))
print((N * (N - 1) * (N - 2) // 6 - complement) % (10 ** 9 + 7))


class DisjointSet:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.total = [1] * N

	def union(self, a, b):
		a_parent = self.find(a)
		b_parent = self.find(b)
		if a_parent != b_parent:
			self.parent[b_parent] = a_parent
			self.total[a_parent] += self.total[b_parent]

	def find(self, a):
		if self.parent[a] != a:
			self.parent[a] = self.find(self.parent[a])
		return self.parent[a]

	def get_total(self, a):
		return self.total[self.find(a)]
N = int(input())
ds = DisjointSet(N)
for i in range(N - 1):
	(x, y, color) = input().split()
	if color == 'b':
		ds.union(int(x) - 1, int(y) - 1)
set_size = {ds.find(i): ds.get_total(i) for i in range(N)}
complement = sum((x * (x - 1) * (N - x) // 2 + x * (x - 1) * (x - 2) // 6 for x in set_size.values()))
print((N * (N - 1) * (N - 2) // 6 - complement) % (10 ** 9 + 7))


class djset:

	def __init__(self, node):
		self.head = node
		self.tail = node
		self.length = 1

class Node:

	def __init__(self, vertex):
		self.vertex = vertex
		self.next = None
		self.parent = None

def MakeSet(node):
	dj = djset(node)
	node.parent = dj

def FindSet(node):
	if node.parent != None:
		return node.parent
	else:
		return None

def UnionSet(node1, node2, dj):
	dj1 = FindSet(node1)
	dj2 = FindSet(node2)
	if dj1 == dj2:
		return
	elif dj1.length < dj2.length:
		if dj2 not in dj:
			dj[dj2] = 1
		if dj1 in dj:
			del dj[dj1]
		UnionHelper(dj1, dj2)
	else:
		if dj1 not in dj:
			dj[dj1] = 1
		if dj2 in dj:
			del dj[dj2]
		UnionHelper(dj2, dj1)

def UnionHelper(dj1, dj2):
	count = 0
	node = dj1.head
	while count < dj1.length:
		node.parent = dj2
		node = node.next
		count += 1
	dj2.tail.next = dj1.head
	dj2.tail = dj1.tail
	dj2.length += dj1.length
n = int(input())
covered = [None] * n
for i in range(n):
	covered[i] = Node(i)
	MakeSet(covered[i])
dj = {}
for _ in range(n - 1):
	line = input().split()
	a = int(line[0]) - 1
	b = int(line[1]) - 1
	c = line[2]
	if c == 'b':
		UnionSet(covered[a], covered[b], dj)
total = n * (n - 1) * (n - 2)
omit = 0
for djset in dj:
	N = djset.length
	omit += N * (N - 1) * (3 * n - 2 * N - 2)
print(int((total - omit) / 6) % (10 ** 9 + 7))


N = int(input())
parents = list(range(N + 1))
sizes = [1] * (N + 1)

def find(x):
	st = list()
	while x != parents[x]:
		st.append(x)
		x = parents[x]
	for y in st:
		parents[y] = x
	return x

def union(x, y):
	ux = find(x)
	uy = find(y)
	if ux != uy:
		parents[uy] = ux
		sizes[ux] += sizes[uy]

def suffix_sum(lst):
	lid = len(lst) - 1
	ss = lst[:]
	for i in range(lid - 1, -1, -1):
		ss[i] += ss[i + 1]
	return ss
for _ in range(N - 1):
	stin = input().split()
	if stin[2] == 'b':
		(x, y) = (int(stin[0]), int(stin[1]))
		union(x, y)
ngr = list((sizes[i] for i in range(1, N + 1) if parents[i] == i))
ss2 = suffix_sum(ngr)
pd2 = list((ngr[i] * ss2[i + 1] for i in range(len(ngr) - 1)))
ss3 = suffix_sum(pd2)
res = sum((ngr[i] * ss3[i + 1] for i in range(len(pd2) - 1)))
print(res % 1000000007)


N = int(input())
Q = N - 1
communities = {i: i for i in range(1, N + 1)}
sizes = {i: 1 for i in range(1, N + 1)}

def community(i):
	j = i
	while communities[j] != j:
		j = communities[j]
	communities[i] = j
	return j

def size(i):
	return sizes[community(i)]

def join(i, j):
	x = [community(i), community(j)]
	if x[0] == x[1]:
		return 0
	else:
		x.sort()
		communities[x[1]] = x[0]
		sizes[x[0]] += sizes[x[1]]
for _ in range(Q):
	instruction = input().split()
	if instruction[2] == 'b':
		(a, b) = (int(instruction[0]), int(instruction[1]))
		join(a, b)
finalsets = []
for i in range(1, N + 1):
	if communities[i] == i:
		finalsets.append(i)
badtrips = 0
for i in finalsets:
	s = sizes[i]
	badtrips += s * (s - 1) * (s - 2) // 6
	badtrips += (N - s) * (s * (s - 1)) // 2
goodtrips = N * (N - 1) * (N - 2) // 6 - badtrips
print(goodtrips % 1000000007)


class DSU:

	def __init__(self, n):
		self.parents = list(range(n))
		self.sizes = [1] * n

	def get(self, n):
		if self.parents[n] != n:
			self.parents[n] = self.get(self.parents[n])
		return self.parents[n]

	def unite(self, n, m):
		n = self.get(n)
		m = self.get(m)
		if n == m:
			return
		if self.sizes[n] > self.sizes[m]:
			(n, m) = (m, n)
		self.parents[n] = m
		self.sizes[m] += self.sizes[n]

	def get_size(self, n):
		return self.sizes[self.get(n)]
n = int(input())
d = DSU(n)
for i in range(n - 1):
	fs = input().split()
	if fs[2] == 'b':
		d.unite(int(fs[0]) - 1, int(fs[1]) - 1)
roots = set((d.get(x) for x in range(n)))
sizes = [d.sizes[r] for r in roots]
histo = [0] * (len(sizes) + 1)
for (i, s) in enumerate(sizes):
	histo[i + 1] = histo[i] + s
h2 = [0] * (len(sizes) + 1)
for (i, s) in enumerate(sizes):
	h2[i] = h2[i - 1] + s * histo[i]
print(sum((s * h2[i - 1] for (i, s) in enumerate(sizes))) % (10 ** 9 + 7))


class DisjointSet:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.total = [1] * N

	def union(self, a, b):
		a_parent = self.find(a)
		b_parent = self.find(b)
		if a_parent != b_parent:
			self.parent[b_parent] = a_parent
			self.total[a_parent] += self.total[b_parent]

	def find(self, a):
		if self.parent[a] != a:
			self.parent[a] = self.find(self.parent[a])
		return self.parent[a]

	def get_total(self, a):
		return self.total[self.find(a)]
N = int(input())
ds = DisjointSet(N)
for i in range(N - 1):
	(x, y, color) = input().split()
	if color == 'b':
		ds.union(int(x) - 1, int(y) - 1)
set_size = {ds.find(i): ds.get_total(i) for i in range(N)}
complement = sum((x * (x - 1) * (N - x) // 2 + x * (x - 1) * (x - 2) // 6 for x in set_size.values()))
print((N * (N - 1) * (N - 2) // 6 - complement) % (10 ** 9 + 7))


class DisjointSet:

	class Node:

		def __init__(self, val):
			self.parent = val
			self.size = 1
			self.rank = 0

	def __init__(self, n):
		self.sets = []
		for i in range(n):
			current = self.Node(i)
			self.sets.append(current)

	def find(self, key):
		if self.sets[key].parent != key:
			self.sets[key].parent = self.find(self.sets[key].parent)
		return self.sets[key].parent

	def union(self, a, b):
		x = self.sets[self.find(a)]
		y = self.sets[self.find(b)]
		if x.rank > y.rank:
			y.parent = x.parent
		else:
			if x.rank == y.rank:
				y.rank += 1
			x.parent = y.parent
		y.size += x.size
		x.size = y.size
n = int(input())
trees = DisjointSet(n)
for i in range(n - 1):
	s = input().split()
	if s[2] == 'b':
		trees.union(int(s[0]) - 1, int(s[1]) - 1)
result = int(n * (n - 1) * (n - 2) / 6)
for i in range(n):
	if trees.sets[i].parent == i:
		k = trees.sets[i].size
		result -= int(k * (k - 1) * (k - 2) / 6)
		result -= int(k * (k - 1) / 2 * (n - k))
result = result % (10 ** 9 + 7)
print(result)


class DisjointSet:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.total = [1] * N

	def union(self, a, b):
		a_parent = self.find(a)
		b_parent = self.find(b)
		if a_parent != b_parent:
			self.parent[b_parent] = a_parent
			self.total[a_parent] += self.total[b_parent]

	def find(self, a):
		if self.parent[a] != a:
			self.parent[a] = self.find(self.parent[a])
		return self.parent[a]

	def get_total(self, a):
		return self.total[self.find(a)]
N = int(input())
ds = DisjointSet(N)
for i in range(N - 1):
	(x, y, color) = input().split()
	if color == 'b':
		ds.union(int(x) - 1, int(y) - 1)
set_size = {ds.find(i): ds.get_total(i) for i in range(N)}
complement = sum((x * (x - 1) * (N - x) // 2 + x * (x - 1) * (x - 2) // 6 for x in set_size.values()))
print((N * (N - 1) * (N - 2) // 6 - complement) % (10 ** 9 + 7))


import math
n = int(input())
parent = [i for i in range(n + 1)]
size = [1] * (n + 1)
flag = set()
tot = 0

def updateParent(x):
	if parent[x] != x:
		parent[x] = updateParent(parent[x])
	return parent[x]

def mergeParent(x, y):
	updateParent(x)
	updateParent(y)
	if parent[x] != parent[y]:
		size[parent[x]] += size[parent[y]]
		parent[parent[y]] = parent[x]

def nc2(x):
	if x >= 2:
		return math.floor(x * (x - 1) / 2)
	return 0

def nc3(x):
	if x >= 3:
		return math.floor(x * (x - 1) * (x - 2) / 6)
	return 0
for i in range(n - 1):
	(x, y, color) = input().split()
	x = int(x)
	y = int(y)
	if color == 'b':
		mergeParent(x, y)
for i in range(1, n + 1):
	parent[i] = updateParent(i)
	if parent[i] not in flag:
		flag.add(parent[i])
		if size[parent[i]] >= 2:
			tot += nc2(size[parent[i]]) * (n - size[parent[i]])
		if size[parent[i]] >= 3:
			tot += nc3(size[parent[i]])
ans = nc3(n) - tot
print(ans % 1000000007)


import math
import sys

def get_root(node, parents):
	if parents[node] == node:
		return node
	return get_root(parents[node], parents)

def union(subroot, root, parents, sizes):
	sizes[root] += sizes[subroot]
	parents[subroot] = root
	del sizes[subroot]

def update_sets(parents, sizes, node1, node2):
	root1 = get_root(node1, parents)
	root2 = get_root(node2, parents)
	if root1 == root2:
		return
	size1 = sizes[root1]
	size2 = sizes[root2]
	if size1 > size2:
		union(root2, root1, parents, sizes)
	else:
		union(root1, root2, parents, sizes)
	return

def nCk(n, k):
	if k > n:
		return 0
	f = math.factorial
	return f(n) / (f(k) * f(n - k))

def compute_triplets(n, sizes):
	num_bad_triplets = 0
	for badset in sizes:
		size = sizes[badset]
		num_bad_triplets += nCk(size, 3) + nCk(size, 2) * (n - size)
	num_good_triples = nCk(n, 3)
	num_triplets = num_good_triples - num_bad_triplets
	return num_triplets
n = int(sys.stdin.readline())
parents = [i for i in range(n)]
sizes = {i: 1 for i in range(n)}
for i in range(n - 1):
	pair = sys.stdin.readline().split(' ')
	node1 = int(pair[0]) - 1
	node2 = int(pair[1]) - 1
	color = pair[2].strip()
	if color == 'b':
		update_sets(parents, sizes, node1, node2)
print(int(compute_triplets(n, sizes) % (10 ** 9 + 7)))


class disjoint_set(object):

	def __init__(self, numelems):
		self.num_sets = numelems
		self.parents = list(range(numelems))
		self.ranks = [0] * numelems
		self.sizes = [1] * numelems

	def num_elems(self):
		return len(self.parents)

	def find(self, elemindex):
		if elemindex < 0 or elemindex >= len(self.parents):
			raise IndexError()
		parent = self.parents[elemindex]
		if parent == elemindex:
			return elemindex
		while True:
			grandparent = self.parents[parent]
			if grandparent == parent:
				return parent
			self.parents[elemindex] = grandparent
			elemindex = parent
			parent = grandparent

	def get_size_of_set(self, elemindex):
		return self.sizes[self.find(elemindex)]

	def are_in_same_set(self, elemindex0, elemindex1):
		return self.find(elemindex0) == self.find(elemindex1)

	def union(self, elemindex0, elemindex1):
		repr0 = self.find(elemindex0)
		repr1 = self.find(elemindex1)
		if repr0 == repr1:
			return False
		cmp = self.ranks[repr0] - self.ranks[repr1]
		if cmp == 0:
			self.ranks[repr0] += 1
		elif cmp < 0:
			(repr0, repr1) = (repr1, repr0)
		self.parents[repr1] = repr0
		self.sizes[repr0] += self.sizes[repr1]
		self.sizes[repr1] = 0
		self.num_sets -= 1
		return True
from functools import reduce
import operator as op

def ncr(n, r):
	r = min(r, n - r)
	if r == 0:
		return 1
	numer = reduce(op.mul, range(n, n - r, -1))
	denom = reduce(op.mul, range(1, r + 1))
	return numer // denom
N = int(input())
dsb = disjoint_set(N)
for _ in range(N - 1):
	(a, b, color) = input().strip().split(' ')
	if color == 'b':
		dsb.union(int(a) - 1, int(b) - 1)
tot = ncr(N, 3)
for i in range(N):
	sub = 0
	if dsb.sizes[i] >= 2:
		sub = (N - dsb.sizes[i]) * ncr(dsb.sizes[i], 2)
		if dsb.sizes[i] >= 3:
			sub += ncr(dsb.sizes[i], 3)
	tot -= sub
print(tot % (10 ** 9 + 7))


def get_class(cl, a):
	x = a
	while cl[x] != x:
		x = cl[x]
	return x

def merge_class(cl, size, a, b):
	a_class = get_class(cl, a)
	b_class = get_class(cl, b)
	if a_class != b_class:
		if size[a_class] < size[b_class]:
			cl[a_class] = b_class
			size[b_class] += size[a_class]
		else:
			cl[b_class] = a_class
			size[a_class] += size[b_class]
n = int(input())
cl = list(range(n))
size = [1] * n
for _ in range(n - 1):
	(a, b, c) = input().split()
	a = int(a) - 1
	b = int(b) - 1
	if c == 'b':
		merge_class(cl, size, a, b)
comp_size = []
for i in range(n):
	if i == cl[i]:
		comp_size.append(size[i])
p1 = 0
p2 = 0
p3 = 0
mod = 1000000007
for x in comp_size:
	p1 = (p1 + x) % mod
	p2 = (p2 + x * x) % mod
	p3 = (p3 + x * x * x) % mod
p111 = p1 * p1 * p1 % mod
p21 = p2 * p1 % mod
q = (p111 - 3 * p21 + 2 * p3) % mod
six_inv = 166666668
print(q * six_inv % mod)


n = int(input())
root = [i for i in range(n + 1)]
size = [1 for _ in range(n + 1)]

def get_root(a):
	while root[a] != a:
		a = root[a]
	return a

def join(a, b):
	roota = get_root(a)
	rootb = get_root(b)
	if size[roota] < size[rootb]:
		(roota, rootb) = (rootb, roota)
	root[rootb] = roota
	size[roota] += size[rootb]
for _ in range(n - 1):
	(a, b, c) = input().split()
	if c == 'b':
		(a, b) = [int(a), int(b)]
		join(a, b)
from collections import Counter
mod = 10 ** 9 + 7
c = Counter((get_root(a) for a in range(1, n + 1)))
ones = [0 for _ in c]
for (i, (k, v)) in enumerate(c.items()):
	if i == 0:
		ones[i] = v
	else:
		ones[i] = (ones[i - 1] + v) % mod
twos = [0 for _ in c]
for (i, (k, v)) in enumerate(c.items()):
	if i == 0:
		twos[i] = 0
	else:
		twos[i] = twos[i - 1] + v * ones[i - 1]
		twos[i] %= mod
threes = [0 for _ in c]
for (i, (k, v)) in enumerate(c.items()):
	if i == 0:
		threes[i] = 0
	else:
		threes[i] = (threes[i - 1] + v * twos[i - 1]) % mod
print(threes[-1])


def binomial(n, k):
	if 0 <= k <= n:
		ntok = 1
		ktok = 1
		for t in range(1, min(k, n - k) + 1):
			ntok *= n
			ktok *= t
			n -= 1
		return ntok // ktok
	else:
		return 0

class Node:

	def __init__(self, label):
		self.label = label
		self.parent = None
		self.count = None

	def __hash__(self):
		return hash(self.label)

	def __eq__(self, other):
		return self.label == other.label

def make_set(x):
	x.parent = x
	x.count = 1

def find(x):
	if x.parent == x:
		return x
	else:
		x.parent = find(x.parent)
		return x.parent

def union(x, y):
	x_root = find(x)
	y_root = find(y)
	if x_root.count > y_root.count:
		y_root.parent = x_root
		x_root.count = x_root.count + y_root.count
	elif x_root.count < y_root.count:
		x_root.parent = y_root
		y_root.count = x_root.count + y_root.count
	elif x_root != y_root:
		y_root.parent = x_root
		x_root.count = x_root.count + y_root.count
vertex = {}
edges = []
N = int(input())
for i in range(N - 1):
	(n1, n2, color) = input().split()
	(n1, n2) = (int(n1), int(n2))
	edges.append((n1, n2, color))
	if n1 not in vertex:
		vertex[n1] = Node(n1)
	if n2 not in vertex:
		vertex[n2] = Node(n2)
for v in vertex:
	make_set(vertex[v])
for (n1, n2, color) in edges:
	if color == 'b':
		if find(vertex[n1]) != find(vertex[n2]):
			union(vertex[n1], vertex[n2])
vertex_num = len(vertex)
black_component_roots = set()
for v in vertex:
	root = find(vertex[v])
	black_component_roots.add(root)
black_component_sizes = list()
for root in black_component_roots:
	black_component_sizes.append(root.count)
num_valid_triplets = binomial(vertex_num, 3)
for black_component_size in black_component_sizes:
	num_valid_triplets -= binomial(black_component_size, 3)
	num_valid_triplets -= binomial(black_component_size, 2) * (vertex_num - black_component_size)
print(num_valid_triplets % (10 ** 9 + 7))


class DisjointSet(object):

	def __init__(self):
		self.parent = None
		self.size = 1
		self.rank = 0

	@staticmethod
	def get_group_parent(node):
		nodes = []
		while node.parent:
			nodes.append(node)
			node = node.parent
		for element in nodes:
			element.parent = node
		return node

	@staticmethod
	def merge_groups(node1, node2):
		root1 = DisjointSet.get_group_parent(node1)
		root2 = DisjointSet.get_group_parent(node2)
		if root1 == root2:
			return
		if root1.rank < root2.rank:
			root1.parent = root2
			root2.size += root1.size
		elif root2.rank < root1.rank:
			root2.parent = root1
			root1.size += root2.size
		else:
			root1.parent = root2
			root2.rank += 1
			root2.size += root1.size
N = int(input())
groups = [DisjointSet() for _ in range(N + 1)]
for _ in range(N - 1):
	(x, y, color) = [a for a in input().split()]
	if color == 'b':
		x = int(x)
		y = int(y)
		DisjointSet.merge_groups(groups[x], groups[y])
sizes = []
for index in range(1, N + 1):
	if not groups[index].parent:
		sizes.append(groups[index].size)
result = 0
if len(sizes) > 2:
	partial = [0 for _ in sizes]
	total = sum(sizes[2:])
	for i in range(2, len(sizes)):
		partial[i] = total
		total -= sizes[i]
	partial2 = [0 for _ in sizes]
	for i in range(1, len(sizes) - 1):
		partial2[i] = sizes[i] * partial[i + 1]
	partial3 = [0 for _ in sizes]
	total = sum(partial2[1:])
	for i in range(1, len(sizes) - 1):
		partial3[i] = total
		total -= partial2[i]
	for i in range(len(sizes) - 2):
		result += sizes[i] * partial3[i + 1]
result %= 10 ** 9 + 7
print(result)


from math import factorial

class DJS(object):

	def __init__(self, n):
		self.n = n
		self.parents = list(range(0, n + 1))
		self.size = [1] * (n + 1)

	def add_elem(self, e1, e2, color):
		if color == 'b':
			(e1, e2) = [int(x) for x in [e1, e2]]
			(parent1, parent2) = (self.parent(e1), self.parent(e2))
			if parent1 != parent2:
				self.union(parent1, parent2)

	def parent(self, e):
		while True:
			if self.parents[e] != e:
				e = self.parents[e]
			else:
				return e

	def union(self, e1, e2):
		if self.size[e1] > self.size[e2]:
			(bigger, smaller) = (e1, e2)
		else:
			(bigger, smaller) = (e2, e1)
		self.parents[smaller] = bigger
		self.size[bigger] += self.size[smaller]

	def b_subtree_sizes(self):
		return [self.size[x] for x in set([self.parent(s) for s in self.parents])]

	@staticmethod
	def nCr(n, r):
		if r > n:
			return 0
		else:
			return factorial(n) / (factorial(n - r) * factorial(r))

	def poss_for_subtree(self, verticies):
		if verticies == 1:
			return 0
		else:
			return self.nCr(verticies, 3) + self.nCr(verticies, 2) * (self.n - verticies)

	def good_triplets(self):
		return self.nCr(self.n, 3) - sum([self.poss_for_subtree(v) for v in self.b_subtree_sizes()])
N = int(input().strip())
my_djs = DJS(N)
for _ in range(1, N):
	args = input().strip().split(' ')
	my_djs.add_elem(*args)
print(int(my_djs.good_triplets() % (1000000000.0 + 7)))


def findParent(x, parents):
	if not parents[x] == x:
		parents[x] = findParent(parents[x], parents)
	return parents[x]

def merge(x, y, parents, size):
	px = findParent(x, parents)
	py = findParent(y, parents)
	if px == py:
		pass
	elif size[px] < size[py]:
		parents[px] = py
		size[py] += size[px]
	else:
		parents[py] = px
		size[px] += size[py]

def selection(n, k):
	if k == n:
		return 1
	elif k > n:
		return 0
	x = 1
	y = 1
	for i in range(k):
		x = x * (n - i)
		y = y * (k - i)
	return x / y
N = int(input())
parents = [i for i in range(N)]
size = [1 for _ in range(N)]
for _ in range(N - 1):
	(x, y, c) = input().strip().split()
	x = int(x) - 1
	y = int(y) - 1
	if c == 'b':
		merge(x, y, parents, size)
total_triple = selection(N, 3)
subs = set()
for p in parents:
	if not p in subs:
		parent = findParent(p, parents)
		if not parent in subs:
			subs.add(parent)
invalid = 0
for s in subs:
	t = size[s]
	invalid += selection(t, 3)
	invalid += selection(t, 2) * (N - t)
count = int(total_triple - invalid)
print(count % (10 ** 9 + 7))


def find(x):
	while uf[x] >= 0:
		if uf[uf[x]] >= 0:
			uf[x] = uf[uf[x]]
		x = uf[x]
	return x
n = int(input())
uf = [-1] * n
for i in range(n - 1):
	(x, y, col) = input().split()
	if col == 'b':
		(x, y) = (find(int(x) - 1), find(int(y) - 1))
		if uf[x] > uf[y]:
			(x, y) = (y, x)
		uf[x] += uf[y]
		uf[y] = x
(a, b, c) = (0, 0, 0)
for i in range(n):
	if uf[i] < 0:
		c -= b * uf[i]
		b -= a * uf[i]
		a -= uf[i]
print(c % int(1000000000.0 + 7))


def find(x):
	while uf[x] >= 0:
		if uf[uf[x]] >= 0:
			uf[x] = uf[uf[x]]
		x = uf[x]
	return x
n = int(input())
uf = [-1] * n
for i in range(n - 1):
	(x, y, col) = input().split()
	if col == 'b':
		(x, y) = (find(int(x) - 1), find(int(y) - 1))
		if uf[x] > uf[y]:
			(x, y) = (y, x)
		uf[x] += uf[y]
		uf[y] = x
(a, b, c) = (0, 0, 0)
for i in range(n):
	if uf[i] < 0:
		c -= b * uf[i]
		b -= a * uf[i]
		a -= uf[i]
print(c % int(1000000000.0 + 7))


class quickUnion:
	l = []
	size = []
	component = []
	large = 2

	def __init__(self, n):
		for i in range(n):
			self.l.append(i)
			self.size.append(1)
			self.component.append(i)

	def root(self, x):
		while self.l[x] != x:
			x = self.l[x]
			self.l[x] = self.l[self.l[x]]
		return x

	def union(self, x, y):
		a = quickUnion.root(self, x)
		b = quickUnion.root(self, y)
		if a == b:
			return
		if self.size[a] > self.size[b]:
			self.l[b] = a
			self.component[b] = -1
			self.size[a] = self.size[a] + self.size[b]
			if self.size[a] > self.large:
				self.large = self.size[a]
		else:
			self.l[a] = b
			self.component[a] = -1
			self.size[b] += self.size[a]
			if self.size[b] > self.large:
				self.large = self.size[b]

	def connected(self, x, y):
		a = quickUnion.root(self, x)
		b = quickUnion.root(self, y)
		if a == b:
			return True
		return False
n = int(input())
m = 1000000007
combo = []
i = 0
test = quickUnion(n)
while i < n - 1:
	count = 0
	(a, b, c) = input().split()
	i += 1
	if c == 'b':
		test.union(int(a) - 1, int(b) - 1)
sub = 0
for el in test.component:
	if el == -1:
		continue
	el = test.size[el]
	if el == 2:
		sub += n - 2
	else:
		temp = el * (el - 1) * (el - 2)
		temp = temp // 6
		temp2 = el * (el - 1)
		temp2 = temp2 * (n - el)
		temp2 = temp2 // 2
		sub += temp + temp2
max = n * (n - 1) * (n - 2)
max = max
max = max // 6
print((max - sub) % m)


from sys import *
from collections import deque
N = int(input().strip())
G = [[] for i in range(N)]
for i in range(N - 1):
	edge = input().strip().split(' ')
	color = edge[2]
	if color == 'b':
		u = int(edge[0])
		v = int(edge[1])
		G[u - 1].append(v - 1)
		G[v - 1].append(u - 1)
C = []
seen = [0 for i in range(N)]
for u in range(N):
	if not seen[u]:
		seen[u] = 1
		nb = 0
		tovisit = deque()
		tovisit.appendleft(u)
		while tovisit:
			node = tovisit.pop()
			nb += 1
			for neighbor in G[node]:
				if not seen[neighbor]:
					seen[neighbor] = 1
					tovisit.appendleft(neighbor)
		C.append(nb)
m = len(C)
S = 0
P = 10 ** 9 + 7
Total = N * (N - 1) * (N - 2) / 6
Bad = 0
for i in range(m):
	if C[i] >= 3:
		Bad += C[i] * (C[i] - 1) * (C[i] - 2) / 6
	if C[i] >= 2:
		Bad += C[i] * (C[i] - 1) / 2 * (N - C[i])
S = int(Total - Bad) % P
print(S)


from itertools import combinations

class DisjointSet:

	def __init__(self, n):
		self.nodes = []
		for i in range(n):
			self.nodes.append(SetNode(i))

	def find(self, node):
		if type(node) is int:
			node = self.nodes[node]
		if node.parent != node:
			node.parent = self.find(node.parent)
		return node.parent

	def merge(self, node1, node2):
		(node1, node2) = (self.find(node1), self.find(node2))
		if node1 == node2:
			return
		(root, child) = (node1, node2)
		if root.rank < child.rank:
			(root, child) = (child, root)
		elif root.rank == child.rank:
			root.rank += 1
		child.parent = root
		root.size += child.size

	def size(self, node):
		return self.find(node).size

class SetNode:

	def __init__(self, i):
		self.parent = self
		self.rank = 0
		self.size = 1
		self.id = i
n = int(input())
black = DisjointSet(n)
for _ in range(n - 1):
	edge = input().split()
	if edge[2] != 'r':
		(i, j) = (int(s) - 1 for s in edge[:2])
		black.merge(i, j)
components = {}
for i in range(n):
	root = black.find(i)
	components[root.id] = root.size
s1 = s2 = s3 = 0
for s in components.values():
	s1 += s
	s2 += s * s1
	s3 += s * s2
triplets = s1 ** 3 - 2 * s1 * s2 + s3
print(triplets % (10 ** 9 + 7))


from functools import reduce
from operator import mul
n = int(input())

def factorial(t):
	return reduce(mul, range(2, t + 1), 1)

def nCr(n, k):
	if n < k:
		return 0
	return factorial(n) // (factorial(k) * factorial(n - k))
nodes = [i for i in range(n)]
cc = {i: [i] for i in range(n)}
for _ in range(n - 1):
	(u, v, c) = input().split()
	(u, v) = map(int, (u, v))
	u -= 1
	v -= 1
	if c == 'b':
		source = nodes[u]
		target = nodes[v]
		if len(cc[source]) > len(cc[target]):
			(source, target) = (target, source)
		for index in cc[source]:
			nodes[index] = target
		cc[target].extend(cc[source])
		del cc[source]
result = nCr(n, 3)
result -= sum((nCr(len(c), 3) + (n - len(c)) * nCr(len(c), 2) for c in cc.values() if len(c) > 1))
print(result % (10 ** 9 + 7))


log = False
n = int(input())
next = list(range(n + 1))
sizes = [1] * (n + 1)

def getgroup(i):
	while next[i] != i:
		i = next[i]
	return i

def solution():
	for i in range(n - 1):
		(n1, n2, c) = input().split(' ')
		n1 = int(n1)
		n2 = int(n2)
		if c == 'b':
			g1 = getgroup(n1)
			g2 = getgroup(n2)
			next[n1] = g1
			next[n2] = g2
			next[g1] = g2
			sizes[g2] += sizes[g1]
			sizes[g1] = 0
		if log:
			print(next[1:], sizes[1:])
	res = 0
	for k in sizes:
		res += k * (k - 1) * (3 * n - 2 * k - 2)
	res = n * (n - 1) * (n - 2) - res
	return int(res / 6) % (10 ** 9 + 7)
if n < 3:
	print(0)
else:
	print(solution())


rank = [0] * 100009
sz = [1] * 100009
root = [0] * 100009

def parent(i):
	if i == root[i]:
		return i
	root[i] = parent(root[i])
	return root[i]

def union(a, b):
	a = parent(a)
	b = parent(b)
	if a != b:
		if rank[a] > rank[b]:
			(a, b) = (b, a)
		root[a] = b
		sz[b] += sz[a]
		if rank[a] == rank[b]:
			rank[b] = rank[b] + 1
n = int(input().rstrip())
edges = []
for i in range(n):
	root[i + 1] = i + 1
for i in range(n - 1):
	inpt = input().rstrip().split()
	inpt[0] = int(inpt[0])
	inpt[1] = int(inpt[1])
	if inpt[2] == 'b':
		union(inpt[0], inpt[1])
	else:
		edges.append((inpt[0], inpt[1]))
M = 10 ** 9 + 7
answer = 0
ar = []
ones_and_twos = 0
for i in range(1, n + 1):
	if sz[i] >= 3 and root[i] == i:
		comp = sz[i]
		comp = comp * (comp - 1) * (comp - 2)
		comp = comp / 6
		comp %= M
		ar.append(comp)
		answer = answer + comp
		answer %= M
	elif sz[i] <= 2 and root[i] == i:
		ones_and_twos += sz[i]
need_twos = []
count = 0
for i in range(1, n + 1):
	if sz[i] >= 2 and root[i] == i:
		need_twos.append(sz[i])
		count = count + sz[i] * (sz[i] - 1) / 2 * (n - sz[i]) % M
		count %= M
answer = n * (n - 1) * (n - 2) / 6 - count - answer
answer %= M
print(int(answer))


from functools import reduce
TNPS = 1000000007

def newpow(x, p):
	if p == 0:
		return 1
	if p == 1:
		return x % TNPS
	return x % TNPS * newpow(x, p - 1) % TNPS

def sumpow(X, p):
	plus = lambda x, y: (x + y) % TNPS
	power = lambda x: newpow(x, p)
	return reduce(plus, list(map(power, X)))

def inv(k):
	if k == 1:
		return 1
	else:
		y = TNPS // k + 1
		x = k * y % TNPS
		return y * inv(x)

def sumprods(X):
	result = pow(sumpow(X, 1), 3)
	result -= 3 * sumpow(X, 2) * sumpow(X, 1) % TNPS
	result = result % TNPS
	result += 2 * sumpow(X, 3)
	result = result % TNPS
	return result * inv(6) % TNPS
N = int(input())
edges = []
col = []
compsizes = []
for j in range(0, N):
	edges.append([])
	col.append(0)
for j in range(1, N):
	nl = input().split()
	if nl[2] == 'b':
		edges[int(nl[0]) - 1].append(int(nl[1]) - 1)
		edges[int(nl[1]) - 1].append(int(nl[0]) - 1)
head = 0
curcomp = 0
while head < N:
	if col[head] == 0:
		stack = [head]
		col[head] = 1
		compsizes.append(0)
		while len(stack) != 0:
			h2 = stack.pop()
			compsizes[curcomp] += 1
			for nb in edges[h2]:
				if col[nb] == 0:
					col[nb] = 1
					stack.append(nb)
		curcomp += 1
	head += 1
print(sumprods(compsizes))


class disjoint_set(object):

	def __init__(self):
		self.parents = []
		self.rank = []
		self.size = []
		self.total_sizes = {1: 0}

	def find(self, x):
		p = self.parents
		if p[x] != x:
			p[x] = self.find(p[x])
		return p[x]

	def add(self, x):
		self.parents.append(len(self.parents))
		self.rank.append(0)
		self.size.append(1)
		self.total_sizes[1] += 1

	def merge(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		x_s = self.size[x]
		y_s = self.size[y]
		self.total_sizes[x_s] -= 1
		self.total_sizes[y_s] -= 1
		if self.rank[x] < self.rank[y]:
			self.parents[x] = y
			self.size[y] += x_s
		else:
			if self.rank[x] == self.rank[y]:
				self.rank[x] += 1
			self.parents[y] = x
			self.size[x] += y_s
		self.total_sizes[x_s + y_s] = self.total_sizes.get(x_s + y_s, 0) + 1

	def find_size(self, x):
		return self.size[self.find(x)]

	def find_minmax(self):
		ma = 0
		mi = len(self.parents)
		for (k, v) in self.total_sizes.items():
			if v > 0:
				ma = max(ma, k)
				mi = min(mi, k)
		return (mi, ma)
n = int(input())
edges = []
for i in range(n - 1):
	edges.append(input().strip().split())
edges = list(map(lambda x: list(map(lambda x: int(x) - 1, x)), list(map(lambda x: x[:2], filter(lambda x: x[2] == 'b', edges)))))
ds = disjoint_set()
for i in range(n):
	ds.add(i)
for (i, j) in edges:
	ds.merge(i, j)
sets = {}
pairs = {}
answer = 0
answer2 = 0
total = 0
pairs_total = 0
for (k, v) in ds.total_sizes.items():
	total += v * k
	sets[k] = v * k
for (k, v) in sets.items():
	pairs_total += v * (total - v)
	pairs[k] = v * (total - v)
pairs_total /= 2
iterator = list(sets.items())
for m in range(len(iterator)):
	k = iterator[m][0]
	v = iterator[m][1]
	answer = int(answer + v * (v - k) * (v - 2 * k) / 6) % 1000000007
	answer = int(answer + v * (v - k) / 2 * (total - v)) % 1000000007
	answer2 = answer2 + v * (pairs_total - pairs[k])
print((answer + int(answer2 / 3)) % 1000000007)


a = []
mod = 10 ** 9 + 7

def find(x):
	while 1:
		if a[x] < 0:
			return x
		else:
			x = a[x]
n = int(input())
a = [-1] * (n + 1)
for q in range(1, n):
	z = [y for y in input().split(' ')]
	if z[2] == 'b':
		p1 = find(int(z[0]))
		p2 = find(int(z[1]))
		if p1 != p2:
			a[p1] = a[p1] + a[p2]
			a[p2] = p1
			a[int(z[1])] = p1
s = 0
for k in range(1, n + 1):
	if a[k] < -1:
		p = -a[k]
		s = s + p * (p - 1) * (n - 2) // 2 % mod
		if -a[k] >= 3:
			s = s - p * (p - 1) * (p - 2) // 3 % mod
print((n * (n - 1) * (n - 2) // 6 - s) % mod)


a = []
mod = 10 ** 9 + 7

def find(x):
	while 1:
		if a[x] < 0:
			return x
		else:
			x = a[x]
n = int(input())
a = [-1] * (n + 1)
for q in range(1, n):
	z = [y for y in input().split(' ')]
	if z[2] == 'b':
		p1 = find(int(z[0]))
		p2 = find(int(z[1]))
		if p1 != p2:
			a[p1] = a[p1] + a[p2]
			a[p2] = p1
			a[int(z[1])] = p1
s = 0
for k in range(1, n + 1):
	if a[k] < -1:
		p = -a[k]
		s = s + p * (p - 1) * (n - 2) // 2 % mod
		if -a[k] >= 3:
			s = s - p * (p - 1) * (p - 2) // 3 % mod
print((n * (n - 1) * (n - 2) // 6 - s) % mod)


from collections import defaultdict

class Union_Find:

	def __init__(self, N):
		self.graph = defaultdict(list)
		self.member_lookup = {}
		self._count = {}
		for i in range(1, N + 1):
			self.graph[i] = [i]
			self.member_lookup[i] = i
			self._count[i] = 0

	def find(self, p):
		return self.member_lookup[p]

	def get_set(self, p):
		return self.graph[self.find(p)]

	def union(self, p, q):
		set_ = self.graph
		i = self.find(p)
		j = self.find(q)
		if i == j:
			return False
		if self._count[i] < self._count[j]:
			(i, j) = (j, i)
		if self._count[i] == 0:
			self._count[i] = 1
		if self._count[j] == 0:
			self._count[j] = 1
		self._count[i] += self._count[j]
		self._count[j] = 0
		set_[i] += set_[j]
		for x in set_[j]:
			self.member_lookup[x] = i
		set_[j] = []
		return True

	def size(self, p):
		return self._count[self.find(p)]

	def get_sizes(self):
		A = []
		for x in self._count.values():
			if x != 0:
				A.append(x)
		return A

	def __str__(self):
		return str(self.graph)

def kundu_and_tree():
	mod = 10 ** 9 + 7
	N = int(input())
	tree = Union_Find(N)
	for _ in range(N - 1):
		line = input().split()
		if line[2] == 'b':
			tree.union(int(line[0]), int(line[1]))
	A = tree.get_sizes()
	result = sum((A[i] * (A[i] - 1) * (3 * N - 2 * A[i] - 2) for i in range(len(A))))
	result = (N * (N - 1) * (N - 2) - result) // 6
	return result % mod
result = kundu_and_tree()
print(result)


from collections import Counter, defaultdict
from functools import reduce, lru_cache
from operator import mul

class UnionFind:

	def __init__(self):
		self.leaders = defaultdict(lambda : None)

	def find(self, x):
		l = self.leaders[x]
		if l is not None:
			while self.leaders[l] is not None:
				l = self.leaders[l]
			self.leaders[x] = l
			return l
		return x

	def union(self, x, y):
		(lx, ly) = (self.find(x), self.find(y))
		if lx != ly:
			self.leaders[lx] = ly

	def get_groups(self):
		groups = defaultdict(set)
		for x in self.leaders:
			groups[self.find(x)].add(x)
		return groups
MOD = 10 ** 9 + 7
uf = UnionFind()
n = int(input())
for _ in range(n - 1):
	(x, y, z) = input().split()
	if z == 'b':
		uf.union(x, y)
grps = [len(g) for g in uf.get_groups().values()]
all_combs = n * (n - 1) * (n - 2) // 6
two_same = [k * (k - 1) * (n - k) // 2 for k in grps]
three_same = [k * (k - 1) * (k - 2) // 6 for k in grps]
print((all_combs - sum(two_same) - sum(three_same)) % MOD)


import math

class Set_Node:

	def __init__(self, value, rank):
		self.value = value
		self.parent = self
		self.rank = rank
		self.total = 1
		self.seen = 0

class Set:

	def makeset(self, val):
		t = Set_Node(val, 0)
		return t

	def findset(self, ptr):
		if ptr == None:
			return None
		else:
			if ptr == ptr.parent:
				return ptr
			ptr.parent = self.findset(ptr.parent)
			return ptr.parent

	def union(self, ptr_x, ptr_y):
		x = self.findset(ptr_x)
		y = self.findset(ptr_y)
		if x.rank > y.rank:
			y.parent = x
			y.child = 1
			x.total += y.total
		elif x.rank < y.rank:
			x.parent = y
			y.total += x.total
			x.child = 1
		else:
			y.parent = x
			x.rank += 1
			x.total += y.total
			y.child = 1
S = Set()
n = int(input())
ptr = {}
max1 = 1
min1 = 1
for i in range(n - 1):
	arr2 = input().split()
	x = int(arr2[0]) - 1
	y = int(arr2[1]) - 1
	if arr2[2] == 'b':
		if x not in ptr:
			ptr[x] = S.makeset(x)
		if y not in ptr:
			ptr[y] = S.makeset(y)
		l = S.findset(ptr[x])
		m = S.findset(ptr[y])
		if l != m:
			S.union(ptr[x], ptr[y])
if n >= 3:
	sum1 = n * (n - 1) * (n - 2) // 6
	for i in ptr:
		if ptr[i].parent == ptr[i]:
			x = ptr[i].total
			if x >= 3:
				sum2 = x * (x - 1) * (x - 2) // 6
				sum1 -= sum2
			sum2 = x * (x - 1) // 2
			sum2 = sum2 * (n - x)
			sum1 -= sum2
	print(sum1 % 1000000007)
else:
	print(0)


def disjoint_set(edges, vertices):

	def MAKE_SET(x):
		return [x]
	sets = [MAKE_SET(v) for v in vertices]
	set_member_lookup = {}
	for (index, v) in enumerate(vertices):
		set_member_lookup[v] = index

	def FIND_SET(x):
		return set_member_lookup[x]

	def UNION(set_u, set_v):
		if sets[set_u] is not None:
			if sets[set_v] is not None:
				sets[set_u].extend(sets[set_v])
				for k in sets[set_v]:
					set_member_lookup[k] = set_u
				sets[set_v] = None
	for (u, v) in edges:
		set_u = FIND_SET(u)
		set_v = FIND_SET(v)
		if set_u != set_v:
			UNION(set_u, set_v)
	return filter(None, sets)
n = int(input())
edges = []
vertices = set()
for _ in range(n - 1):
	data = input().split()
	if data[2] == 'b':
		edges.append((int(data[0]), int(data[1])))
	vertices.add(int(data[0]))
	vertices.add(int(data[1]))
num = 0
total = n * (n - 1) * (n - 2) / 6
for b in disjoint_set(edges, vertices):
	lb = len(b)
	num += lb * (lb - 1) * (n - lb) / 2
	if lb >= 3:
		num += lb * (lb - 1) * (lb - 2) / 6
print(int(total - num) % 1000000007)


class Node:

	def __init__(self, id):
		self.id = id
		self.parent = self
		self.rank = 0
		self.size = 1

	def __repr__(self):
		return 'Node({!r})'.format(self.id)

def Find(x):
	if x.parent is not x:
		x.parent = Find(x.parent)
	return x.parent

def Union(x, y):
	xroot = Find(x)
	yroot = Find(y)
	if xroot is yroot:
		return
	if xroot.rank < yroot.rank:
		(xroot, yroot) = (yroot, xroot)
	yroot.parent = xroot
	xroot.size += yroot.size
	if xroot.rank == yroot.rank:
		xroot.rank = xroot.rank + 1

def main():
	N = int(input())
	nodes = {}
	from collections import Counter
	for _ in range(N - 1):
		(x, y, z) = input().split()
		if z == 'b':
			node1 = nodes.setdefault(int(x), Node(int(x)))
			node2 = nodes.setdefault(int(y), Node(int(y)))
			Union(node1, node2)
	T = Counter((Find(n).id for n in nodes.values()))
	t = 0
	for S in T.values():
		t += S * (S - 1) * (3 * N - 2 * S - 2)
	print((N * (N - 1) * (N - 2) - t) // 6 % (10 ** 9 + 7))
main()


class DisjointSet:

	def __init__(self, n=0):
		self.parents = list(range(n))
		self.sizes = [1] * n
		self.elts = {}
		for i in range(n):
			self.elts[i + 1] = i

	def makeSet(self, elt):
		n = self.size()
		self.elts[elt] = n
		self.sizes.append(1)
		self.parents.append(n)

	def size(self):
		return len(self.parents)

	def subsetSize(self, elt):
		try:
			return self.sizes[self.__find(self.elts[elt])]
		except KeyError:
			return -1

	def subsetSizes(self):
		roots = list(set([self.__find(i) for i in range(self.size())]))
		return [self.sizes[i] for i in roots]

	def __find(self, i):
		if self.parents[i] != i:
			self.parents[i] = self.__find(self.parents[i])
		return self.parents[i]

	def union(self, elt1, elt2):
		try:
			root1 = self.__find(self.elts[elt1])
			root2 = self.__find(self.elts[elt2])
		except KeyError:
			return
		if root1 != root2:
			if self.sizes[root2] > self.sizes[root1]:
				(root1, root2) = (root2, root1)
			self.parents[root2] = root1
			self.sizes[root1] += self.sizes[root2]

def binom(n, k):
	if k < 0 or k > n:
		return 0
	elif k == 0:
		return 1
	else:
		return n * binom(n - 1, k - 1) // k
N = int(input())
blackComps = DisjointSet(N)
for _ in range(N - 1):
	(n1, n2, col) = input().split()
	n1 = int(n1)
	n2 = int(n2)
	if col == 'b':
		blackComps.union(n1, n2)
n_triplets = binom(N, 3)
for s in blackComps.subsetSizes():
	if s > 1:
		n_triplets -= binom(s, 3)
		n_triplets -= binom(s, 2) * (N - s)
print(n_triplets % (10 ** 9 + 7))


class DisjointSet:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.total = [1] * N

	def union(self, a, b):
		a_parent = self.find(a)
		b_parent = self.find(b)
		if a_parent != b_parent:
			self.parent[b_parent] = a_parent
			self.total[a_parent] += self.total[b_parent]

	def find(self, a):
		if self.parent[a] != a:
			self.parent[a] = self.find(self.parent[a])
		return self.parent[a]

	def get_total(self, a):
		return self.total[self.find(a)]
N = int(input())
ds = DisjointSet(N)
for i in range(N - 1):
	(x, y, color) = input().split()
	if color == 'b':
		ds.union(int(x) - 1, int(y) - 1)
set_size = {ds.find(i): ds.get_total(i) for i in range(N)}
complement = sum((x * (x - 1) * (N - x) // 2 + x * (x - 1) * (x - 2) // 6 for x in set_size.values()))
print((N * (N - 1) * (N - 2) // 6 - complement) % (10 ** 9 + 7))


import sys
from collections import Counter
import math
from itertools import combinations

def find_root(id, cc_id):
	while id != cc_id[id]:
		id = cc_id[id]
	return id

def binom(n, k):
	if n < k:
		return 0
	if n == k:
		return 1
	return math.factorial(n) / (math.factorial(k) * math.factorial(n - k))
n = int(input())
cc_id = list(range(n))
rank = Counter(cc_id)
for _ in range(n - 1):
	edge = input().split(' ')
	if edge[2] == 'b':
		id1 = find_root(int(edge[0]) - 1, cc_id)
		id2 = find_root(int(edge[1]) - 1, cc_id)
		if rank[id1] < rank[id2]:
			(id1, id2) = (id2, id1)
		cc_id[id2] = id1
		rank[id1] += rank[id2]
cc_sizes = []
for i in range(n):
	if i == cc_id[i]:
		cc_sizes.append(rank[i])
total = binom(n, 3)
for t in cc_sizes:
	total -= binom(t, 3) + binom(t, 2) * (n - t)
if total > 10 ** 9 + 7:
	total = total % (10 ** 9 + 7)
print(int(total))


import math
M = 1000000007

def compact(numbers):
	count = dict()
	for n in numbers:
		count[n] = count.get(n, 0) + 1
	keys = list(sorted(count.keys()))
	values = [count[k] for k in keys]
	return (keys, values)

def bfs(adjlist, start):
	visited = set()
	if start not in adjlist:
		return visited
	queue = [start]
	while queue:
		u = queue.pop()
		if u not in visited:
			visited.add(u)
			queue.extend(adjlist[u])
	return visited

def get_components(adjlist):
	nodes = set(adjlist.keys())
	components = list()
	while nodes:
		u = nodes.pop()
		visited = bfs(adjlist, u)
		for v in visited:
			if v != u:
				nodes.remove(v)
		components.append(visited)
	return components

def to_adjlist(graph):
	(nodes, edges) = graph
	adjlist = dict(((n, set()) for n in nodes))
	for (u, v) in edges:
		adjlist[u].add(v)
		adjlist[v].add(u)
	return adjlist

def choose(a, b):
	if a < b:
		return 0
	else:
		return math.factorial(a) // math.factorial(a - b) // math.factorial(b)

def solve(problem):
	((nodes, edges), colors) = problem
	n = len(nodes)
	black_edges = [e for (e, c) in zip(edges, colors) if c == 'b']
	black_adjlist = to_adjlist((nodes, black_edges))
	black_components = get_components(black_adjlist)
	(g, h) = compact(list(map(len, black_components)))
	m = len(g)
	acc = 0
	for i in range(m):
		acc += choose(h[i], 3) * g[i] ** 3 % M
	for i in range(m):
		for j in range(m):
			if i != j:
				acc += h[i] * (h[i] - 1) * h[j] * g[i] ** 2 * g[j] // 2 % M
	for i in range(m - 2):
		for j in range(i + 1, m - 1):
			for k in range(j + 1, m):
				acc += h[i] * h[j] * h[k] * g[i] * g[j] * g[k] % M
	return acc % M

def parse():
	n = int(input())
	nodes = list(range(1, n + 1))
	edges = list()
	edge_colors = list()
	for i in range(n - 1):
		(*e, color) = input().split()
		e = tuple(map(int, e))
		edges.append(e)
		edge_colors.append(color)
	return ((nodes, edges), edge_colors)
problem = parse()
print(solve(problem))


class PathCompression:

	def __init__(self, n):
		self.data = [int(x) for x in range(0, n)]
		self.weight = [1] * n
		self.components = n

	def find(self, p):
		while p != self.data[p]:
			self.data[p] = self.data[self.data[p]]
			p = self.data[p]
		return p

	def connected(self, p, q):
		return self.find(p) == self.find(q)

	def union(self, p, q):
		rootP = self.find(p)
		rootQ = self.find(q)
		if rootP == rootQ:
			return
		elif self.weight[rootP] < self.weight[rootQ]:
			self.data[rootP] = rootQ
			self.weight[rootQ] += self.weight[rootP]
		else:
			self.data[rootQ] = rootP
			self.weight[rootP] += self.weight[rootQ]
		self.components -= 1

def add_mod(a, b, m):
	return (a % m + b % m) % m

def minus_mod(a, b, m):
	return (a % m - b % m) % m

def multiply_mod(a, b, m):
	return a % m * b % m % m

def solver1(counter, nodes):
	(c, result) = (1000000007, 0)
	total_triplets_comb = nodes * (nodes - 1) * (nodes - 2) / 6
	for count in counter:
		(comb2, comb_n) = (0, 0)
		if count > 2:
			comb_n += count * (count - 1) * (count - 2) / 6
		comb2 = count * (count - 1) / 2
		result += comb_n + comb2 * (nodes - count)
	return int(minus_mod(total_triplets_comb, result, c))

def solver2(counter):
	mod = 1000000007
	nodes = len(counter)
	res = 0
	for i in range(0, nodes):
		for j in range(i + 1, nodes):
			for k in range(j + 1, nodes):
				res = add_mod(res, multiply_mod(multiply_mod(counter[i], counter[j], mod), counter[k], mod), mod)
	return res

def run():
	nodes = int(input())
	path_c = PathCompression(nodes + 1)
	for i in range(1, nodes):
		(u, v, c) = list(input().split(' '))
		if c == 'b':
			path_c.union(int(u), int(v))
	counter = []
	for i in range(1, nodes + 1):
		if path_c.data[i] == i:
			counter.append(path_c.weight[i])
	print(solver1(counter, nodes))
run()


class DisjointSet:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.total = [1] * N

	def union(self, a, b):
		a_parent = self.find(a)
		b_parent = self.find(b)
		if a_parent != b_parent:
			self.parent[b_parent] = a_parent
			self.total[a_parent] += self.total[b_parent]

	def find(self, a):
		if self.parent[a] != a:
			self.parent[a] = self.find(self.parent[a])
		return self.parent[a]

	def get_total(self, a):
		return self.total[self.find(a)]
N = int(input())
ds = DisjointSet(N)
for i in range(N - 1):
	(x, y, color) = input().split()
	if color == 'b':
		ds.union(int(x) - 1, int(y) - 1)
set_size = {ds.find(i): ds.get_total(i) for i in range(N)}
bad_trips = sum((x * (x - 1) * (N - x) // 2 + x * (x - 1) * (x - 2) // 6 for x in set_size.values()))
total_combs = N * (N - 1) * (N - 2) // 6
valid_trips = (total_combs - bad_trips) % (10 ** 9 + 7)
print(valid_trips)


N = int(input())
sigma3 = N * (N - 1) * (N - 2) // 6
comp = [set()] + [set([i]) for i in range(1, N + 1)]
compindex = {i: i for i in range(1, N + 1)}
for i in range(N - 1):
	t = input()
	extrem = list(map(int, t[:-2].split()))
	if t[-1] == 'b':
		(i, j) = extrem
		(a, b) = (len(comp[compindex[i]]), len(comp[compindex[j]]))
		sigma3 -= a * b * (N - a - b)
		if a < b:
			for x in comp[compindex[i]]:
				compindex[x] = compindex[j]
				comp[compindex[j]].add(x)
		else:
			for x in comp[compindex[j]]:
				compindex[x] = compindex[i]
				comp[compindex[i]].add(x)
print(sigma3 % (10 ** 9 + 7))


from collections import deque
from typing import List, Union, Deque
RED = 'r'
BLACK = 'b'

class Node:
	__slots__ = ('name', 'tier', 'red_edges', 'black_edges')

	def __init__(self, name):
		self.name = name
		self.tier = 1
		self.red_edges = []
		self.black_edges = []

	def iter_edges(self):
		for node in self.red_edges:
			yield (node, RED)
		for node in self.black_edges:
			yield (node, BLACK)

	def __repr__(self):
		edges = ['r:%s' % p.name for p in self.red_edges] + ['b:%s' % p.name for p in self.black_edges]
		if edges:
			return 'Node(%s, %s)' % (self.name, edges)
		else:
			return 'Node(%s)' % self.name

def add_edge(A: Node, B: Node, color: str):
	assert color in (RED, BLACK)
	if color == RED:
		A.red_edges.append(B)
		B.red_edges.append(A)
	else:
		A.black_edges.append(B)
		B.black_edges.append(A)

def merge_black_edges(tree: Node):
	qu = deque([tree])
	while qu:
		cur = qu.popleft()
		if cur.black_edges:
			black_qu = deque(cur.black_edges)
			cur.black_edges = []
			while black_qu:
				next = black_qu.popleft()
				cur.red_edges.extend(next.red_edges)
				cur.tier += 1
				black_qu.extend(next.black_edges)
		qu.extend(cur.red_edges)

def calc_num_triplets(nodes: List[Node]):
	if not nodes:
		return 0
	tree = convert_to_tree(nodes[0])
	merge_black_edges(tree)
	qu = deque([tree])
	tiers = []
	while qu:
		cur = qu.popleft()
		tiers.append(cur.tier)
		qu.extend(cur.red_edges)
	N = len(tiers)
	sum_tiers = list(tiers)
	for k in range(N - 2, -1, -1):
		sum_tiers[k] += sum_tiers[k + 1]
	assert sum_tiers[0] == sum(tiers)
	sum_tiers2 = [0] * N
	for k in range(N - 2, -1, -1):
		sum_tiers2[k] = sum_tiers2[k + 1] + tiers[k] * sum_tiers[k + 1]
	r = 0
	for xx in range(N - 1):
		r += tiers[xx] * sum_tiers2[xx + 1]
	return r

def convert_to_tree(root_node):
	qu = deque([root_node])
	qu_parent = deque([None])
	while qu:
		cur = qu.popleft()
		parent = qu_parent.popleft()
		if parent in cur.red_edges:
			cur.red_edges.remove(parent)
		if parent in cur.black_edges:
			cur.black_edges.remove(parent)
		qu.extend(cur.red_edges)
		qu.extend(cur.black_edges)
		qu_parent.extend([cur] * (len(cur.red_edges) + len(cur.black_edges)))
	return root_node

def run():
	N = int(input())
	nodes = [Node(k) for k in range(N)]
	for _ in range(N - 1):
		(u, v, clr) = input().split()
		u = int(u) - 1
		v = int(v) - 1
		add_edge(nodes[u], nodes[v], clr)
	num_triplets = calc_num_triplets(nodes)
	print(num_triplets % (10 ** 9 + 7))
run()


class UnionFind(object):

	def __init__(self, N):
		self.N = N
		self.sizes = [None] + [1] * N
		self.paren = [None] + [i for i in range(1, N + 1)]
		self.roots = set([i for i in range(1, N + 1)])

	def union(self, x, y):
		u = self.find(x)
		v = self.find(y)
		if u != v:
			if self.sizes[u] > self.sizes[v]:
				tmp = u
				u = v
				v = tmp
			self.paren[u] = v
			self.roots.remove(u)
			self.sizes[v] += self.sizes[u]

	def find(self, x):
		root = x
		while self.paren[root] != root:
			root = self.paren[root]
		curr = x
		while curr != root:
			self.paren[curr] = root
			curr = self.paren[curr]
		return root

	def sizeOf(self, x):
		return self.sizes[self.find(x)]

	def getRoots(self):
		return self.roots

def numTriplets(uf):
	roots = uf.getRoots()
	N = len(roots)
	root_sizes = []
	for root in roots:
		root_sizes.append(uf.sizeOf(root))
	r_sums = [0] * N
	r_sum = 0
	for i in range(N - 1, -1, -1):
		r_sum += root_sizes[i]
		r_sums[i] = r_sum
	twoChoices = [0] * N
	for i in range(N - 2, -1, -1):
		twoChoices[i] = twoChoices[i + 1] + root_sizes[i] * r_sums[i + 1]
	threeChoices = [0] * N
	for i in range(N - 2, -1, -1):
		threeChoices[i] = threeChoices[i + 1] + root_sizes[i] * twoChoices[i + 1]
	return threeChoices[0] % (10 ** 9 + 7)
N = int(input())
uf = UnionFind(N)
for _ in range(N - 1):
	[u, v, c] = input().split()
	if c == 'b':
		uf.union(int(u), int(v))
print(numTriplets(uf))


import collections
BIG_PRIME = 10 ** 9 + 7
total = 0
edges = collections.defaultdict(list)
q = []
p_q = []
parent = {}
children = collections.defaultdict(list)
node_num = collections.defaultdict(int)
branch_num = collections.defaultdict(int)
n = int(input())
for i in range(n - 1):
	(a, b, color) = input().split()
	edges[a].append((b, color))
	edges[b].append((a, color))
root = next(iter(edges.keys()))
parent[root] = 'Root'
q.append(root)
p_q.append(root)
for node in q:
	node_num[node] = 1
	for (i, color) in edges[node]:
		if i != parent[node]:
			if color == 'r':
				q.append(i)
				parent[i] = node
				children[node].append(i)
			else:
				node_num[node] += 1
				for (j, color2) in edges[i]:
					if j != node:
						edges[node].append((j, color2))
						edges[j].remove((i, color2))
						edges[j].append((node, color2))
total = n * (n - 1) * (n - 2) // 6 % BIG_PRIME
for i in q:
	total = (total - node_num[i] * (node_num[i] - 1) * (node_num[i] - 2) // 6) % BIG_PRIME
	total = (total - node_num[i] * (node_num[i] - 1) * (n - node_num[i]) // 2) % BIG_PRIME
print(total)


from collections import defaultdict

def solve(n, vertices):
	parents = [i for i in range(n)]
	sizes = [1 for i in range(n)]

	def getParent(a):
		if parents[a] == a:
			return a
		pa = getParent(parents[a])
		parents[a] = pa
		return pa

	def merge(a, b):
		pa = getParent(a)
		pb = getParent(b)
		if sizes[pa] > sizes[pb]:
			parents[pb] = pa
			sizes[pa] += sizes[pb]
		else:
			parents[pa] = pb
			sizes[pb] += sizes[pa]
	for (a, b, c) in vertices:
		if c != 'r':
			merge(a, b)
	for i in range(n):
		getParent(i)
	groups = set(parents)
	(s, p, t) = (0, 0, 0)
	for g in groups:
		(s, p, t) = (s + sizes[g], p + s * sizes[g], t + p * sizes[g])
	return t % (10 ** 9 + 7)
n = int(input())
vertices = []
for _ in range(n - 1):
	(a, b, c) = input().split()
	(a, b) = (int(a) - 1, int(b) - 1)
	vertices.append((a, b, c))
print(solve(n, vertices))


MOD = 1000000007
n = int(input())
edges = []
parent = {}
size = {}
for i in range(1, n + 1):
	parent[i] = i
	size[i] = 1

def find(x):
	if parent[x] != x:
		parent[x] = find(parent[x])
	return parent[x]

def union(x, y):
	xr = find(x)
	yr = find(y)
	if size[xr] > size[yr]:
		(xr, yr) = (yr, xr)
	parent[xr] = yr
	size[yr] += size[xr]

def nc2(n):
	return int(n * (n - 1) / 2)

def nc3(n):
	return int(n * (n - 1) * (n - 2) / 6)
for i in range(n - 1):
	line = input().split()
	line[:2] = map(int, line[:2])
	line[2] = True if line[2] == 'r' else False
	edges.append(tuple(line))
for (a, b, color) in edges:
	if not color:
		union(a, b)
bad = 0
for i in range(1, n + 1):
	if parent[i] == i:
		bad += nc3(size[i]) % MOD + nc2(size[i]) * (n - size[i]) % MOD
print((nc3(n) - bad) % MOD)


class DisjointSet:

	def __init__(self, n):
		self.parent = list(range(n + 1))
		self.size = [1] * (n + 1)
		self.rank = [1] * (n + 1)

	def find(self, idx):
		if self.parent[idx] != idx:
			self.parent[idx] = self.find(self.parent[idx])
		return self.parent[idx]

	def union(self, a, b):
		parent_a = self.find(a)
		parent_b = self.find(b)
		if parent_a == parent_b:
			return
		if self.rank[parent_a] > self.rank[parent_b]:
			self.parent[parent_b] = parent_a
			self.size[parent_a] += self.size[parent_b]
			self.size[parent_b] = 0
		else:
			self.parent[parent_a] = parent_b
			self.size[parent_b] += self.size[parent_a]
			self.size[parent_a] = 0
			if self.rank[parent_a] == self.rank[parent_b]:
				self.rank[parent_b] += 1

	def setSize(self, idx):
		parent = self.find(idx)
		return self.size[parent]

def choose3Frome(n):
	return n * (n - 1) * (n - 2) // 6

def choose2From(n):
	return n * (n - 1) // 2
n = int(input())
m = 10 ** 9 + 7
disjointSet = DisjointSet(n)
for _ in range(n - 1):
	query = list(input().rstrip().split())
	if query[2] == 'b':
		(a, b) = (int(query[0]), int(query[1]))
		disjointSet.union(a, b)
res = choose3Frome(n)
for idx in range(1, len(disjointSet.size)):
	size = disjointSet.size[idx]
	if size > 2:
		res -= choose3Frome(size)
	if size > 1:
		res -= choose2From(size) * (n - size)
print(res % m)


class DisjointSet:

	def __init__(self, n):
		self.parent = list(range(n))
		self.rank = [0] * n

	def union(self, i, j):
		(pi, pj) = (self.find(i), self.find(j))
		if pi == pj:
			return
		(ri, rj) = (self.rank[pi], self.rank[pj])
		if ri < rj:
			self.parent[pi] = pj
		elif ri > rj:
			self.parent[pj] = pi
		else:
			self.parent[pi] = pj
			self.rank[pj] += 1

	def find(self, i):
		if self.parent[i] != i:
			self.parent[i] = self.find(self.parent[i])
		return self.parent[i]

def kundu(n, uvc):
	djs = DisjointSet(n)
	for (u, v, c) in uvc:
		if c == 'b':
			djs.union(u - 1, v - 1)
	size = [0] * n
	for v in range(n):
		size[djs.find(v)] += 1
	triplets = n * (n - 1) * (n - 2) // 6
	for v in range(n):
		triplets -= size[v] * (size[v] - 1) * (size[v] - 2) // 6
		triplets -= size[v] * (size[v] - 1) * (n - size[v]) // 2
	return triplets % (10 ** 9 + 7)
n = int(input())
uvc = []
for _ in range(n - 1):
	(us, vs, c) = input().split()
	uvc.append((int(us), int(vs), c))
print(kundu(n, uvc))


class DisjointSet:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.total = [1] * N

	def union(self, a, b):
		a_parent = self.find(a)
		b_parent = self.find(b)
		if a_parent != b_parent:
			self.parent[b_parent] = a_parent
			self.total[a_parent] += self.total[b_parent]

	def find(self, a):
		if self.parent[a] != a:
			self.parent[a] = self.find(self.parent[a])
		return self.parent[a]

	def get_total(self, a):
		return self.total[self.find(a)]
N = int(input())
ds = DisjointSet(N)
for i in range(N - 1):
	(x, y, color) = input().split()
	if color == 'b':
		ds.union(int(x) - 1, int(y) - 1)
set_size = {ds.find(i): ds.get_total(i) for i in range(N)}
complement = sum((x * (x - 1) * (N - x) // 2 + x * (x - 1) * (x - 2) // 6 for x in set_size.values()))
print((N * (N - 1) * (N - 2) // 6 - complement) % (10 ** 9 + 7))


class DisjointSet:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.total = [1] * N

	def union(self, a, b):
		a_parent = self.find(a)
		b_parent = self.find(b)
		if a_parent != b_parent:
			self.parent[b_parent] = a_parent
			self.total[a_parent] += self.total[b_parent]

	def find(self, a):
		if self.parent[a] != a:
			self.parent[a] = self.find(self.parent[a])
		return self.parent[a]

	def get_total(self, a):
		return self.total[self.find(a)]
N = int(input())
ds = DisjointSet(N)
for i in range(N - 1):
	(x, y, color) = input().split()
	if color == 'b':
		ds.union(int(x) - 1, int(y) - 1)
set_size = {ds.find(i): ds.get_total(i) for i in range(N)}
complement = sum((x * (x - 1) * (N - x) // 2 + x * (x - 1) * (x - 2) // 6 for x in set_size.values()))
print((N * (N - 1) * (N - 2) // 6 - complement) % (10 ** 9 + 7))


n = int(input())
edges = []
i = 0
for i in range(n - 1):
	edges.append(input().split(' '))

class UF:

	def __init__(self, n):
		self.name = list((x for x in range(n + 1)))
		self.parent = list((x for x in range(n + 1)))
		self.size = list((1 for x in range(n + 1)))

	def find(self, x):
		if self.parent[x] != x:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, x, y):
		xRoot = self.find(x)
		yRoot = self.find(y)
		if xRoot == yRoot:
			return
		if self.size[xRoot] >= self.size[yRoot]:
			self.parent[yRoot] = xRoot
			self.size[xRoot] += self.size[yRoot]
			self.size[yRoot] = 0
		else:
			self.parent[xRoot] = yRoot
			self.size[yRoot] += self.size[xRoot]
			self.size[xRoot] = 0
n = len(edges) + 1
node = UF(n)
for (n1, n2, c) in edges:
	if c == 'b':
		node.union(int(n1), int(n2))
bGroup = []
for i in range(n + 1):
	if node.size[i] > 1:
		bGroup.append(node.size[i])
bPerm = 0
for i in bGroup:
	bPerm += i * (i - 1) // 2 * (n - i)
	if i > 2:
		bPerm += i * (i - 1) * (i - 2) // 6
totPerm = n * (n - 1) * (n - 2) // 6
result = totPerm - bPerm
mod = 10 ** 9 + 7
print(result % mod)


class Node:

	def __init__(self, parent, size):
		self.parent = parent
		self.size = size

class union_join:

	def __init__(self, num):
		self.arr = [Node(0, 0) for _ in range(num)]
		self.elements = num
		for (i, node) in enumerate(self.arr):
			node.parent = i + 1
			node.size = 1

	def root(self, index):
		while self.arr[index].parent != index + 1:
			self.arr[index].parent = self.arr[self.arr[index].parent - 1].parent
			index = self.arr[index].parent - 1
		return index

	def join(self, left, right):
		left_root = self.root(left - 1)
		right_root = self.root(right - 1)
		self.arr[right_root].parent = left_root + 1
		self.arr[left_root].size += self.arr[right_root].size

	def print(self):
		for i in range(self.elements):
			print('parent ', self.arr[i].parent, ' size ', self.arr[i].size)

	def get(self, index):
		return self.arr[index]
(num_nodes, left_id, right_id, position) = (0, 0, 0, 0)
edge = ''
combinations = 0
num_nodes = int(input())
combinations = num_nodes * (num_nodes - 1) * (num_nodes - 2) / 6
sets = union_join(num_nodes)
for _ in range(num_nodes - 1):
	(left_id, right_id, edge) = input().split(' ')
	if edge == 'b':
		sets.join(int(left_id), int(right_id))
for i in range(num_nodes):
	parent = sets.get(i).parent
	size = sets.get(i).size
	bad_edges = 0
	if parent == i + 1 and size != 1:
		bad_edges = size * (size - 1) * (size - 2) / 6
		choose = size * (size - 1) / 2
		choose *= num_nodes - size
		bad_edges += choose
	combinations -= bad_edges
print(int(combinations) % 1000000007)


class Node:

	def __init__(self, parent, size):
		self.parent = parent
		self.size = size

class union_join:

	def __init__(self, num):
		self.arr = [Node(0, 0) for _ in range(num)]
		self.elements = num
		for (i, node) in enumerate(self.arr):
			node.parent = i + 1
			node.size = 1

	def root(self, index):
		while self.arr[index].parent != index + 1:
			self.arr[index].parent = self.arr[self.arr[index].parent - 1].parent
			index = self.arr[index].parent - 1
		return index

	def join(self, left, right):
		left_root = self.root(left - 1)
		right_root = self.root(right - 1)
		self.arr[right_root].parent = left_root + 1
		self.arr[left_root].size += self.arr[right_root].size

	def print(self):
		for i in range(self.elements):
			print('parent ', self.arr[i].parent, ' size ', self.arr[i].size)

	def get(self, index):
		return self.arr[index]
(num_nodes, left_id, right_id, position) = (0, 0, 0, 0)
edge = ''
combinations = 0
num_nodes = int(input())
combinations = num_nodes * (num_nodes - 1) * (num_nodes - 2) // 6
sets = union_join(num_nodes)
for _ in range(num_nodes - 1):
	(left_id, right_id, edge) = input().split(' ')
	if edge == 'b':
		sets.join(int(left_id), int(right_id))
for i in range(num_nodes):
	parent = sets.get(i).parent
	size = sets.get(i).size
	bad_edges = 0
	if parent == i + 1 and size != 1:
		bad_edges = size * (size - 1) * (size - 2) // 6
		choose = size * (size - 1) // 2
		choose *= num_nodes - size
		bad_edges += choose
	combinations -= bad_edges
print(combinations % 1000000007)


class Node:

	def __init__(self, parent, size):
		self.parent = parent
		self.size = size

class union_join:

	def __init__(self, num):
		self.arr = [Node(0, 0) for _ in range(num)]
		self.elements = num
		for (i, node) in enumerate(self.arr):
			node.parent = i + 1
			node.size = 1

	def root(self, index):
		while self.arr[index].parent != index + 1:
			self.arr[index].parent = self.arr[self.arr[index].parent - 1].parent
			index = self.arr[index].parent - 1
		return index

	def join(self, left, right):
		left_root = self.root(left - 1)
		right_root = self.root(right - 1)
		self.arr[right_root].parent = left_root + 1
		self.arr[left_root].size += self.arr[right_root].size

	def print(self):
		for i in range(self.elements):
			print('parent ', self.arr[i].parent, ' size ', self.arr[i].size)

	def get(self, index):
		return self.arr[index]
(num_nodes, left_id, right_id, position) = (0, 0, 0, 0)
edge = ''
combinations = 0
num_nodes = int(input())
combinations = num_nodes * (num_nodes - 1) * (num_nodes - 2) // 6
sets = union_join(num_nodes)
for _ in range(num_nodes - 1):
	(left_id, right_id, edge) = input().split(' ')
	if edge == 'b':
		sets.join(int(left_id), int(right_id))
for i in range(num_nodes):
	parent = sets.get(i).parent
	size = sets.get(i).size
	bad_edges = 0
	if parent == i + 1 and size != 1:
		bad_edges = size * (size - 1) * (size - 2) // 6
		choose = size * (size - 1) // 2
		choose *= num_nodes - size
		bad_edges += choose
	combinations -= bad_edges
print(combinations % 1000000007)


from collections import defaultdict
import collections, sys
MOD = 1000000007

def connected_components(lists):
	neighbors = defaultdict(set)
	seen = set()
	for each in lists:
		for item in each:
			neighbors[item].update(each)

	def component(node, neighbors=neighbors, seen=seen, see=seen.add):
		nodes = set([node])
		next_node = nodes.pop
		while nodes:
			node = next_node()
			see(node)
			nodes |= neighbors[node] - seen
			yield node
	for node in neighbors:
		if node not in seen:
			yield sorted(component(node))
n = int(input())
blackEdges = []
temp = ''
for i in range(n):
	line = sys.stdin.readline().strip()
	if line.endswith('b'):
		blackEdges.append(list(map(int, line[:-2].split())))
connectedBlack = connected_components(blackEdges)
totalTriplets = n * (n - 1) * (n - 2) // 6
notValid = sum((len(t) * (len(t) - 1) * (3 * n - 2 * len(t) - 2) // 6 for t in connectedBlack))
print((totalTriplets - notValid) % MOD)


class DisjointSet:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.total = [1] * N

	def union(self, a, b):
		a_parent = self.find(a)
		b_parent = self.find(b)
		if a_parent != b_parent:
			self.parent[b_parent] = a_parent
			self.total[a_parent] += self.total[b_parent]

	def find(self, a):
		if self.parent[a] != a:
			self.parent[a] = self.find(self.parent[a])
		return self.parent[a]

	def get_total(self, a):
		return self.total[self.find(a)]
N = int(input())
ds = DisjointSet(N)
for i in range(N - 1):
	(x, y, color) = input().split()
	if color == 'b':
		ds.union(int(x) - 1, int(y) - 1)
set_size = {ds.find(i): ds.get_total(i) for i in range(N)}
complement = sum((x * (x - 1) * (N - x) // 2 + x * (x - 1) * (x - 2) // 6 for x in set_size.values()))
print((N * (N - 1) * (N - 2) // 6 - complement) % (10 ** 9 + 7))


import itertools

def findParent(i):
	children = []
	while parents[i] != i:
		children.append(i)
		i = parents[i]
	for j in children:
		parents[j] = i
	return i

def merge(i, j):
	i = findParent(i)
	j = findParent(j)
	if i != j:
		if sizes[i] < sizes[j]:
			parents[i] = j
			sizes[j] += sizes[i]
		else:
			parents[j] = i
			sizes[i] += sizes[j]
n = int(input())
parents = list(range(n + 1))
sizes = [1] * (n + 1)
for _ in range(n - 1):
	q = input().split()
	if q[2] == 'b':
		merge(int(q[0]), int(q[1]))
p = 10 ** 9 + 7
finalsizes = [sizes[i] for i in range(1, n + 1) if parents[i] == i]
leftsizesums = finalsizes.copy()
rightsizesums = finalsizes.copy()
for i in range(1, len(finalsizes)):
	leftsizesums[i] += leftsizesums[i - 1]
	rightsizesums[-(i + 1)] += rightsizesums[-i]
count = 0
for i in range(1, len(finalsizes) - 1):
	count = (count + finalsizes[i] * leftsizesums[i - 1] * rightsizesums[i + 1]) % p
print(count)


import collections, sys
MOD = 1000000007

def connected_components(lists):
	neighbors = collections.defaultdict(set)
	seen = set()
	for each in lists:
		for item in each:
			neighbors[item].update(each)

	def component(node, neighbors=neighbors, seen=seen, see=seen.add):
		nodes = set([node])
		next_node = nodes.pop
		while nodes:
			node = next_node()
			see(node)
			nodes |= neighbors[node] - seen
			yield node
	for node in neighbors:
		if node not in seen:
			yield sorted(component(node))
N = int(sys.stdin.readline())
if N < 3:
	print(0)
else:
	edges = []
	for _ in range(N - 1):
		line = sys.stdin.readline().strip()
		if line.endswith('b'):
			edges.append(list(map(int, line[:-2].split())))
	subtrees = connected_components(edges)
	invalid = sum((len(t) * (len(t) - 1) * (3 * N - 2 * len(t) - 2) // 6 for t in subtrees))
	total = N * (N - 1) * (N - 2) // 6
	print((total - invalid) % MOD)


n = int(input())
p = list(range(n))
rank = [0] * n
size = [1] * n

def get(v):
	stack = []
	while p[v] != v:
		stack.append(v)
		v = p[v]
	for u in stack:
		p[u] = v
	return v

def union(v1, v2):
	v1 = get(v1)
	v2 = get(v2)
	if v1 == v2:
		return
	if rank[v1] < rank[v2]:
		(v1, v2) = (v2, v1)
	size[v1] += size[v2]
	p[v2] = v1
	rank[v1] += 1
for _ in range(n - 1):
	(x, y, col) = input().split()
	if col == 'b':
		union(int(x) - 1, int(y) - 1)
a = [size[i] for i in range(n) if p[i] == i]
MOD = 10 ** 9 + 7

def solve(a):
	s1 = [0]
	for x in a:
		s1.append((s1[-1] + x) % MOD)
	s2 = [0]
	for (i, x) in enumerate(a):
		s2.append((s2[-1] + x * s1[i]) % MOD)
	s3 = [0]
	for (i, x) in enumerate(a):
		s3.append((s3[-1] + x * s2[i]) % MOD)
	return s3[-1]
print(solve(a))