You are given a rooted tree with N nodes and the root of the tree, R, is also given. Each node of the tree contains a value, that is initially empty. You have to mantain the tree under two operations:

Update Operation
Report Operation

Update Operation 

Each Update Operation begins with the character U. Character U is followed by 3 integers T, V and K. For every node which is the descendent of the node T, update it's value by adding V + d*K, where V and K are the parameters of the query and d is the distance of the node from T. Note that V is added to node T.  

Report Operation 

Each Report Operation begins with the character Q. Character Q is followed by 2 integers, A and B. Output the sum of values of nodes in the path from A to B modulo ($10^{9}$ + 7)  

Input Format 

The first Line consists of 3 space separated integers, N E R, where N is the number of nodes present, E is the total number of queries (update + report), and R is root of the tree.  

Each of the next N-1 lines contains 2 space separated integers, X and Y (X and Y are connected by an edge).

Thereafter, E lines follows: each line can represent either the Update Operation or the Report Operation.

Update Operation is of the form : U T V K.
Report Operation is of the form : Q A B.

Output Format 

Output the answer for every given report operation.

Constraints  

1 ≤ N, E ≤ $10^{5} $

1 ≤ E ≤ $10^{5} $

1 ≤ R, X, Y, T, A, B ≤ N 

1 ≤ V, K ≤ $10^{9} $

X ≠ Y

Sample Input

7 7 1
1 2
2 3
2 4
2 5
5 6
6 7
U 5 10 2
U 4 5 3
Q 1 7
U 6 7 4
Q 2 7
Q 1 4
Q 2 4

Sample Output

36
54
5
5

Explanation  

Values of Nodes after U 5 10 2: [0 0 0 0 10 12 14].
Values of Nodes after U 4 5 3: [0 0 0 5 10 12 14]. 
Sum of the Nodes from 1 to 7: 0 + 0 + 10 + 12 + 14 = 36.
Values of Nodes after U 6 7 4: [0 0 0 5 10 19 25].  
Sum of the Nodes from 2 to 7: 0 + 10 + 19 + 25 = 54. 
Sum of the Nodes from 1 to 4: 0 + 0 + 5 = 5.
Sum of the Nodes from 2 to 4: 0 + 5 = 5.

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Data structures


Solutions:
class Node(object):

	def __init__(self, value=0, parent=None):
		self.children = set()
		self.parent = parent
		self.value = value
		self.update = set()

	def addUpdate(self, arr):
		self.update.add((arr[0], arr[1]))

	def addChild(self, node):
		self.children.add(node)

	def setParent(self, node):
		self.parent = node

def root_path(bottom):
	chain = []
	while bottom is not None:
		chain.append(bottom)
		bottom = bottom.parent
	return chain

def height(bottom, top):
	res = 1
	while bottom != top and bottom is not None:
		bottom = bottom.parent
		res += 1
	return res

def q2(arr, nodes):
	(a, b) = arr
	first = nodes[a - 1]
	last = nodes[b - 1]
	path = root_path(last)
	h = height(last, first)
	res = 0
	while len(path) > 0:
		h = min(h, len(path))
		d = max(len(path) - h, 0)
		c = path.pop()
		for u in c.update:
			for i in range(h):
				res += (u[0] + (d + i) * u[1]) % (10 ** 9 + 7)
	return res % (10 ** 9 + 7)

def isRootBetween(bottom, top):
	if bottom == top:
		return False
	if bottom in root_path(top):
		return False
	if top in root_path(bottom):
		return False
	return True

def isDeeper(x, y):
	p = y
	while p is not None:
		if x == p:
			return False
		p = p.parent
	return True

def query(arr, nodes, root):
	(a, b) = arr
	x = nodes[a - 1]
	y = nodes[b - 1]
	if a == b == root:
		return q2([root, root], nodes)
	if isRootBetween(x, y):
		return (q2([root, a], nodes) + q2([root, b], nodes) - q2([root, root], nodes)) % (10 ** 9 + 7)
	elif isDeeper(x, y):
		return q2([b, a], nodes)
	else:
		return q2([a, b], nodes)

def update(arr, nodes):
	node = nodes[arr[0] - 1]
	node.addUpdate(arr[1:])
line1 = [int(x) for x in input().split(' ')]
nodes = [Node() for i in range(line1[0])]
root = line1[2] - 1

def add_in_dict(d, k, v):
	if d.get(k) is None:
		d[k] = [v]
	else:
		d[k] += {v}
tmp = dict()
for i in range(line1[0] - 1):
	(p, c) = [int(x) for x in input().split(' ')]
	add_in_dict(tmp, p - 1, c - 1)
	add_in_dict(tmp, c - 1, p - 1)
visited = []
parents = [root]
while len(parents) > 0:
	current = parents.pop()
	ltmp = tmp.get(current)
	if ltmp is not None:
		for c in ltmp:
			if c not in visited:
				nodes[c].setParent(nodes[current])
				nodes[current].addChild(nodes[c])
				parents.append(c)
	visited.append(current)
for i in range(line1[1]):
	inp = input().split(' ')
	t = inp[0]
	integers = [int(x) for x in inp[1:]]
	if t == 'U':
		update(integers, nodes)
	else:
		print(query(integers, nodes, root + 1))


class Node(object):

	def __init__(self, value=0, parent=None):
		self.children = set()
		self.parent = parent
		self.value = value
		self.update = set()

	def addUpdate(self, arr):
		self.update.add((arr[0], arr[1]))

	def addChild(self, node):
		self.children.add(node)

	def setParent(self, node):
		self.parent = node

def root_path(bottom):
	chain = []
	while bottom is not None:
		chain.append(bottom)
		bottom = bottom.parent
	return chain

def height(bottom, top):
	res = 1
	while bottom != top and bottom is not None:
		bottom = bottom.parent
		res += 1
	return res

def q2(arr, nodes):
	(a, b) = arr
	first = nodes[a - 1]
	last = nodes[b - 1]
	path = root_path(last)
	h = height(last, first)
	res = 0
	while len(path) > 0:
		h = min(h, len(path))
		d = max(len(path) - h, 0)
		c = path.pop()
		for u in c.update:
			for i in range(h):
				res += (u[0] + (d + i) * u[1]) % (10 ** 9 + 7)
	return res % (10 ** 9 + 7)

def isRootBetween(bottom, top):
	if bottom == top:
		return False
	if bottom in root_path(top):
		return False
	if top in root_path(bottom):
		return False
	return True

def isDeeper(x, y):
	p = y
	while p is not None:
		if x == p:
			return False
		p = p.parent
	return True

def query(arr, nodes, root):
	(a, b) = arr
	x = nodes[a - 1]
	y = nodes[b - 1]
	if a == b == root:
		return q2([root, root], nodes)
	if isRootBetween(x, y):
		return (q2([root, a], nodes) + q2([root, b], nodes) - q2([root, root], nodes)) % (10 ** 9 + 7)
	elif isDeeper(x, y):
		return q2([b, a], nodes)
	else:
		return q2([a, b], nodes)

def update(arr, nodes):
	node = nodes[arr[0] - 1]
	node.addUpdate(arr[1:])
line1 = [int(x) for x in input().split(' ')]
nodes = [Node() for i in range(line1[0])]
root = line1[2] - 1

def add_in_dict(d, k, v):
	if d.get(k) is None:
		d[k] = [v]
	else:
		d[k] += {v}
tmp = dict()
for i in range(line1[0] - 1):
	(p, c) = [int(x) for x in input().split(' ')]
	add_in_dict(tmp, p - 1, c - 1)
	add_in_dict(tmp, c - 1, p - 1)
visited = []
parents = [root]
while len(parents) > 0:
	current = parents.pop()
	ltmp = tmp.get(current)
	if ltmp is not None:
		for c in ltmp:
			if c not in visited:
				nodes[c].setParent(nodes[current])
				nodes[current].addChild(nodes[c])
				parents.append(c)
	visited.append(current)
for i in range(line1[1]):
	inp = input().split(' ')
	t = inp[0]
	integers = [int(x) for x in inp[1:]]
	if t == 'U':
		update(integers, nodes)
	else:
		print(query(integers, nodes, root + 1))


class Node:

	def __init__(self, key):
		self.key = key
		self.high = 0
		self.data = 0
		self.nexts = []
		self.previous = None

def update(head, V, K, d):
	if head is None:
		return
	head.data += V + d * K
	for n in head.nexts:
		update(n, V, K, d + 1)

def report(start, end, root):
	if start is None or end is None:
		return
	limit = pow(10, 9) + 7
	higherNode = start
	lowerNode = end
	if start.high < end.high:
		higherNode = end
		lowerNode = start
	distance = higherNode.high - lowerNode.high
	_sum = 0
	while higherNode.high > lowerNode.high:
		_sum += higherNode.data
		if _sum > limit:
			_sum %= limit
		higherNode = higherNode.previous
	while higherNode.data != lowerNode.data:
		_sum += higherNode.data
		_sum += lowerNode.data
		if _sum > limit:
			_sum %= limit
		higherNode = higherNode.previous
		lowerNode = lowerNode.previous
	_sum += higherNode.data
	if _sum > limit:
		_sum %= limit
	print(_sum)

def correctVector(head, high):
	if head is None:
		return
	for node in head.nexts:
		node.previous = head
		node.nexts.remove(head)
		node.high = high
		correctVector(node, high + 1)

def resolve(data):
	configs = data[0].split(' ')
	N = int(configs[0])
	E = int(configs[1])
	root = configs[2]
	nodes = {}
	for i in range(1, N):
		items = data[i].split(' ')
		first = items[0]
		second = items[1]
		if first in nodes:
			firstNode = nodes[first]
		else:
			firstNode = Node(first)
			nodes[first] = firstNode
		if second in nodes:
			secondNode = nodes[second]
		else:
			secondNode = Node(second)
			nodes[second] = secondNode
		firstNode.nexts.append(secondNode)
		secondNode.nexts.append(firstNode)
	correctVector(nodes[root], 1)
	for i in range(N, N + E):
		items = data[i].split(' ')
		itemType = items[0]
		if itemType == 'U':
			update(nodes[items[1]], int(items[2]), int(items[3]), 0)
		elif itemType == 'Q':
			report(nodes[items[1]], nodes[items[2]], nodes[root])
import sys
data = [s.strip() for s in sys.stdin]
resolve(data)


import math
import os
import random
import re
import sys
sys.setrecursionlimit(1000000)
from collections import defaultdict, deque

class RootedTree:

	def __init__(self, R, edges):
		self.ROOT = R
		self.edges = edges
		self.node_value = defaultdict(int)
		self.parent = {node: -1 for node in edges.keys()}
		self.children = defaultdict(list)
		self.build_tree()

	def build_tree(self):
		queue = deque([self.ROOT])
		self.parent[self.ROOT] = None
		while queue:
			node = queue.popleft()
			for neigh in self.edges[node]:
				if self.parent[neigh] == -1:
					queue.append(neigh)
					self.parent[neigh] = node
					self.children[node].append(neigh)

	def update(self, T, V, K):
		this_level = set([T])
		next_level = set()
		d = 0
		while this_level:
			node = this_level.pop()
			self.node_value[node] = (self.node_value[node] + V + d * K) % 1000000007
			next_level.update(self.children[node])
			if this_level == set():
				this_level = set(next_level)
				next_level = set()
				d += 1

	def find_path(self, A, B):
		if A == B:
			return [B]
		path_ROOT_B = [B]
		parent = self.parent[B]
		while parent != None and parent != A:
			path_ROOT_B = [parent] + path_ROOT_B
			parent = self.parent[parent]
		if parent == A:
			return [A] + path_ROOT_B
		path_A_ROOT = []
		node = A
		while node not in path_ROOT_B:
			path_A_ROOT.append(node)
			node = self.parent[node]
		idx = path_ROOT_B.index(node)
		path_A_ROOT.extend(path_ROOT_B[idx:])
		return path_A_ROOT

	def report(self, A, B):
		path = self.find_path(A, B)
		if path:
			return sum([self.node_value[node] for node in path]) % 1000000007
		else:
			return 0

	def __str__(self):
		for (idx, key) in enumerate(self.grid.keys()):
			print(self.grid[key], end=' ')
			if idx % self.LEN == self.LEN - 1:
				print()
(N, E, R) = map(int, input().split())
edges = defaultdict(set)
parent = {}
for _ in range(N - 1):
	(u, v) = map(int, input().split())
	if v == R:
		edges[v].add(u)
	elif u == R:
		edges[u].add(v)
	else:
		edges[u].add(v)
		edges[v].add(u)
tree = RootedTree(R, edges)
for _ in range(E):
	query = input()
	if query[0] == 'U':
		(T, V, K) = map(int, query[2:].split())
		tree.update(T, V, K)
	else:
		(A, B) = map(int, query[2:].split())
		print(tree.report(A, B))


class Node(object):

	def __init__(self, value=0, parent=None):
		self.children = set()
		self.parent = parent
		self.value = value
		self.update = set()

	def addUpdate(self, arr):
		self.update.add((arr[0], arr[1]))

	def addChild(self, node):
		self.children.add(node)

	def setParent(self, node):
		self.parent = node

def root_path(bottom):
	chain = []
	while bottom is not None:
		chain.append(bottom)
		bottom = bottom.parent
	return chain

def height(bottom, top):
	res = 1
	while bottom != top and bottom is not None:
		bottom = bottom.parent
		res += 1
	return res

def q2(arr, nodes):
	(a, b) = arr
	first = nodes[a - 1]
	last = nodes[b - 1]
	path = root_path(last)
	h = height(last, first)
	res = 0
	while len(path) > 0:
		h = min(h, len(path))
		d = max(len(path) - h, 0)
		c = path.pop()
		for u in c.update:
			for i in range(h):
				res += (u[0] + (d + i) * u[1]) % (10 ** 9 + 7)
	return res % (10 ** 9 + 7)

def isRootBetween(bottom, top):
	if bottom == top:
		return False
	if bottom in root_path(top):
		return False
	if top in root_path(bottom):
		return False
	return True

def isDeeper(x, y):
	p = y
	while p is not None:
		if x == p:
			return False
		p = p.parent
	return True

def query(arr, nodes, root):
	(a, b) = arr
	x = nodes[a - 1]
	y = nodes[b - 1]
	if a == b == root:
		return q2([root, root], nodes)
	if isRootBetween(x, y):
		return (q2([root, a], nodes) + q2([root, b], nodes) - q2([root, root], nodes)) % (10 ** 9 + 7)
	elif isDeeper(x, y):
		return q2([b, a], nodes)
	else:
		return q2([a, b], nodes)

def update(arr, nodes):
	node = nodes[arr[0] - 1]
	node.addUpdate(arr[1:])
line1 = [int(x) for x in input().split(' ')]
nodes = [Node() for i in range(line1[0])]
root = line1[2] - 1

def add_in_dict(d, k, v):
	if d.get(k) is None:
		d[k] = [v]
	else:
		d[k] += {v}
tmp = dict()
for i in range(line1[0] - 1):
	(p, c) = [int(x) for x in input().split(' ')]
	add_in_dict(tmp, p - 1, c - 1)
	add_in_dict(tmp, c - 1, p - 1)
visited = []
parents = [root]
while len(parents) > 0:
	current = parents.pop()
	ltmp = tmp.get(current)
	if ltmp is not None:
		for c in ltmp:
			if c not in visited:
				nodes[c].setParent(nodes[current])
				nodes[current].addChild(nodes[c])
				parents.append(c)
	visited.append(current)
for i in range(line1[1]):
	inp = input().split(' ')
	t = inp[0]
	integers = [int(x) for x in inp[1:]]
	if t == 'U':
		update(integers, nodes)
	else:
		print(query(integers, nodes, root + 1))


class Node(object):

	def __init__(self, value=0, parent=None):
		self.children = set()
		self.parent = parent
		self.value = value
		self.update = set()

	def addUpdate(self, arr):
		self.update.add((arr[0], arr[1]))

	def addChild(self, node):
		self.children.add(node)

	def setParent(self, node):
		self.parent = node

def root_path(bottom):
	chain = []
	while bottom is not None:
		chain.append(bottom)
		bottom = bottom.parent
	return chain

def height(bottom, top):
	res = 1
	while bottom != top and bottom is not None:
		bottom = bottom.parent
		res += 1
	return res

def q2(arr, nodes):
	(a, b) = arr
	first = nodes[a - 1]
	last = nodes[b - 1]
	path = root_path(last)
	h = height(last, first)
	res = 0
	while len(path) > 0:
		h = min(h, len(path))
		d = max(len(path) - h, 0)
		c = path.pop()
		for u in c.update:
			for i in range(h):
				res += (u[0] + (d + i) * u[1]) % (10 ** 9 + 7)
	return res % (10 ** 9 + 7)

def isRootBetween(bottom, top):
	if bottom == top:
		return False
	if bottom in root_path(top):
		return False
	if top in root_path(bottom):
		return False
	return True

def isDeeper(x, y):
	p = y
	while p is not None:
		if x == p:
			return False
		p = p.parent
	return True

def query(arr, nodes, root):
	(a, b) = arr
	x = nodes[a - 1]
	y = nodes[b - 1]
	if a == b == root:
		return q2([root, root], nodes)
	if isRootBetween(x, y):
		return (q2([root, a], nodes) + q2([root, b], nodes) - q2([root, root], nodes)) % (10 ** 9 + 7)
	elif isDeeper(x, y):
		return q2([b, a], nodes)
	else:
		return q2([a, b], nodes)

def update(arr, nodes):
	node = nodes[arr[0] - 1]
	node.addUpdate(arr[1:])
line1 = [int(x) for x in input().split(' ')]
nodes = [Node() for i in range(line1[0])]
root = line1[2] - 1

def add_in_dict(d, k, v):
	if d.get(k) is None:
		d[k] = [v]
	else:
		d[k] += {v}
tmp = dict()
for i in range(line1[0] - 1):
	(p, c) = [int(x) for x in input().split(' ')]
	add_in_dict(tmp, p - 1, c - 1)
	add_in_dict(tmp, c - 1, p - 1)
visited = []
parents = [root]
while len(parents) > 0:
	current = parents.pop()
	ltmp = tmp.get(current)
	if ltmp is not None:
		for c in ltmp:
			if c not in visited:
				nodes[c].setParent(nodes[current])
				nodes[current].addChild(nodes[c])
				parents.append(c)
	visited.append(current)
for i in range(line1[1]):
	inp = input().split(' ')
	t = inp[0]
	integers = [int(x) for x in inp[1:]]
	if t == 'U':
		update(integers, nodes)
	else:
		print(query(integers, nodes, root + 1))


(n, e, r) = map(int, input().split(' '))
tree = {}
values = {}
parent = {}
level = {}
level[r] = 0
tree[r] = []

def peek(stack):
	return stack[len(stack) - 1]

def removeparent(tree, root, parent):
	stack = [[root, -1]]
	for i in tree[root]:
		parent[i] = root
	while stack != []:
		if len(stack) > 1:
			for i in range(len(tree[peek(stack)[0]])):
				if tree[peek(stack)[0]][i] == stack[len(stack) - 2][0]:
					parent[peek(stack)[0]] = tree[peek(stack)[0]][i]
					tree[peek(stack)[0]].pop(i)
					break
		if peek(stack)[1] == len(tree[peek(stack)[0]]) - 1:
			stack.pop()
			continue
		temp = peek(stack)[1] + 1
		stack.append([tree[peek(stack)[0]][temp], -1])
		level[peek(stack)[0]] = len(stack) - 1
		stack[len(stack) - 2][1] = temp

def update(tree, values, t, v, k):
	stack = [[t, -1]]
	values[t] += v
	while stack != []:
		if peek(stack)[1] == len(tree[peek(stack)[0]]) - 1:
			stack.pop()
			continue
		temp = peek(stack)[1] + 1
		stack.append([tree[peek(stack)[0]][temp], -1])
		stack[len(stack) - 2][1] = temp
		values[peek(stack)[0]] += v + k * (len(stack) - 1)

def report(tree, a, b):
	summ = 0
	sum1 = values[b]
	sum2 = values[a]
	nexa = a
	nexb = b
	if level[a] > level[b]:
		for i in range(1, level[a] - level[b] + 1):
			nexa = parent[nexa]
			sum2 += values[nexa]
	elif level[b] > level[a]:
		for i in range(1, level[b] - level[a] + 1):
			nexb = parent[nexb]
			sum1 += values[nexb]
	while nexa != nexb:
		nexa = parent[nexa]
		sum2 += values[nexa]
		nexb = parent[nexb]
		sum1 += values[nexb]
	return (sum1 + sum2 - values[nexa]) % (10 ** 9 + 7)
for i in range(n - 1):
	(a, b) = map(int, input().split(' '))
	if not a in tree:
		tree[a] = [b]
	else:
		tree[a].append(b)
	if not b in tree:
		tree[b] = [a]
	else:
		tree[b].append(a)
	values[a] = 0
	values[b] = 0
removeparent(tree, r, parent)
for _ in range(e):
	q = input().split(' ')
	if q[0] == 'U':
		update(tree, values, int(q[1]), int(q[2]), int(q[3]))
	else:
		print(report(tree, int(q[1]), int(q[2])))


class Node(object):

	def __init__(self, value=0, parent=None):
		self.children = set()
		self.parent = parent
		self.value = value
		self.update = set()

	def addUpdate(self, arr):
		self.update.add((arr[0], arr[1]))

	def addChild(self, node):
		self.children.add(node)

	def setParent(self, node):
		self.parent = node

def root_path(bottom):
	chain = []
	while bottom is not None:
		chain.append(bottom)
		bottom = bottom.parent
	return chain

def height(bottom, top):
	res = 1
	while bottom != top and bottom is not None:
		bottom = bottom.parent
		res += 1
	return res

def q2(arr, nodes):
	(a, b) = arr
	first = nodes[a - 1]
	last = nodes[b - 1]
	path = root_path(last)
	h = height(last, first)
	res = 0
	while len(path) > 0:
		h = min(h, len(path))
		d = max(len(path) - h, 0)
		c = path.pop()
		for u in c.update:
			for i in range(h):
				res += (u[0] + (d + i) * u[1]) % (10 ** 9 + 7)
	return res % (10 ** 9 + 7)

def isRootBetween(bottom, top):
	if bottom == top:
		return False
	if bottom in root_path(top):
		return False
	if top in root_path(bottom):
		return False
	return True

def isDeeper(x, y):
	p = y
	while p is not None:
		if x == p:
			return False
		p = p.parent
	return True

def query(arr, nodes, root):
	(a, b) = arr
	x = nodes[a - 1]
	y = nodes[b - 1]
	if a == b == root:
		return q2([root, root], nodes)
	if isRootBetween(x, y):
		return (q2([root, a], nodes) + q2([root, b], nodes) - q2([root, root], nodes)) % (10 ** 9 + 7)
	elif isDeeper(x, y):
		return q2([b, a], nodes)
	else:
		return q2([a, b], nodes)

def update(arr, nodes):
	node = nodes[arr[0] - 1]
	node.addUpdate(arr[1:])
line1 = [int(x) for x in input().split(' ')]
nodes = [Node() for i in range(line1[0])]
root = line1[2] - 1

def add_in_dict(d, k, v):
	if d.get(k) is None:
		d[k] = [v]
	else:
		d[k] += {v}
tmp = dict()
for i in range(line1[0] - 1):
	(p, c) = [int(x) for x in input().split(' ')]
	add_in_dict(tmp, p - 1, c - 1)
	add_in_dict(tmp, c - 1, p - 1)
visited = []
parents = [root]
while len(parents) > 0:
	current = parents.pop()
	ltmp = tmp.get(current)
	if ltmp is not None:
		for c in ltmp:
			if c not in visited:
				nodes[c].setParent(nodes[current])
				nodes[current].addChild(nodes[c])
				parents.append(c)
	visited.append(current)
for i in range(line1[1]):
	inp = input().split(' ')
	t = inp[0]
	integers = [int(x) for x in inp[1:]]
	if t == 'U':
		update(integers, nodes)
	else:
		print(query(integers, nodes, root + 1))


class Node(object):

	def __init__(self, value=0, parent=None):
		self.children = set()
		self.parent = parent
		self.value = value
		self.update = set()

	def addUpdate(self, arr):
		self.update.add((arr[0], arr[1]))

	def addChild(self, node):
		self.children.add(node)

	def setParent(self, node):
		self.parent = node

def root_path(bottom):
	chain = []
	while bottom is not None:
		chain.append(bottom)
		bottom = bottom.parent
	return chain

def height(bottom, top):
	res = 1
	while bottom != top and bottom is not None:
		bottom = bottom.parent
		res += 1
	return res

def q2(arr, nodes):
	(a, b) = arr
	first = nodes[a - 1]
	last = nodes[b - 1]
	path = root_path(last)
	h = height(last, first)
	res = 0
	while len(path) > 0:
		h = min(h, len(path))
		d = max(len(path) - h, 0)
		c = path.pop()
		for u in c.update:
			for i in range(h):
				res += (u[0] + (d + i) * u[1]) % (10 ** 9 + 7)
	return res % (10 ** 9 + 7)

def isRootBetween(bottom, top):
	if bottom == top:
		return False
	if bottom in root_path(top):
		return False
	if top in root_path(bottom):
		return False
	return True

def isDeeper(x, y):
	p = y
	while p is not None:
		if x == p:
			return False
		p = p.parent
	return True

def query(arr, nodes, root):
	(a, b) = arr
	x = nodes[a - 1]
	y = nodes[b - 1]
	if a == b == root:
		return q2([root, root], nodes)
	if isRootBetween(x, y):
		return (q2([root, a], nodes) + q2([root, b], nodes) - q2([root, root], nodes)) % (10 ** 9 + 7)
	elif isDeeper(x, y):
		return q2([b, a], nodes)
	else:
		return q2([a, b], nodes)

def update(arr, nodes):
	node = nodes[arr[0] - 1]
	node.addUpdate(arr[1:])
line1 = [int(x) for x in input().split(' ')]
nodes = [Node() for i in range(line1[0])]
root = line1[2] - 1

def add_in_dict(d, k, v):
	if d.get(k) is None:
		d[k] = [v]
	else:
		d[k] += {v}
tmp = dict()
for i in range(line1[0] - 1):
	(p, c) = [int(x) for x in input().split(' ')]
	add_in_dict(tmp, p - 1, c - 1)
	add_in_dict(tmp, c - 1, p - 1)
visited = []
parents = [root]
while len(parents) > 0:
	current = parents.pop()
	ltmp = tmp.get(current)
	if ltmp is not None:
		for c in ltmp:
			if c not in visited:
				nodes[c].setParent(nodes[current])
				nodes[current].addChild(nodes[c])
				parents.append(c)
	visited.append(current)
for i in range(line1[1]):
	inp = input().split(' ')
	t = inp[0]
	integers = [int(x) for x in inp[1:]]
	if t == 'U':
		update(integers, nodes)
	else:
		print(query(integers, nodes, root + 1))


class Node(object):

	def __init__(self, value=0, parent=None):
		self.children = set()
		self.parent = parent
		self.value = value
		self.update = set()

	def addUpdate(self, arr):
		self.update.add((arr[0], arr[1]))

	def addChild(self, node):
		self.children.add(node)

	def setParent(self, node):
		self.parent = node

def root_path(bottom):
	chain = []
	while bottom is not None:
		chain.append(bottom)
		bottom = bottom.parent
	return chain

def height(bottom, top):
	res = 1
	while bottom != top and bottom is not None:
		bottom = bottom.parent
		res += 1
	return res

def q2(arr, nodes):
	(a, b) = arr
	first = nodes[a - 1]
	last = nodes[b - 1]
	path = root_path(last)
	h = height(last, first)
	res = 0
	while len(path) > 0:
		h = min(h, len(path))
		d = max(len(path) - h, 0)
		c = path.pop()
		for u in c.update:
			for i in range(h):
				res += (u[0] + (d + i) * u[1]) % (10 ** 9 + 7)
	return res % (10 ** 9 + 7)

def isRootBetween(bottom, top):
	if bottom == top:
		return False
	if bottom in root_path(top):
		return False
	if top in root_path(bottom):
		return False
	return True

def isDeeper(x, y):
	p = y
	while p is not None:
		if x == p:
			return False
		p = p.parent
	return True

def query(arr, nodes, root):
	(a, b) = arr
	x = nodes[a - 1]
	y = nodes[b - 1]
	if a == b == root:
		return q2([root, root], nodes)
	if isRootBetween(x, y):
		return (q2([root, a], nodes) + q2([root, b], nodes) - q2([root, root], nodes)) % (10 ** 9 + 7)
	elif isDeeper(x, y):
		return q2([b, a], nodes)
	else:
		return q2([a, b], nodes)

def update(arr, nodes):
	node = nodes[arr[0] - 1]
	node.addUpdate(arr[1:])
line1 = [int(x) for x in input().split(' ')]
nodes = [Node() for i in range(line1[0])]
root = line1[2] - 1

def add_in_dict(d, k, v):
	if d.get(k) is None:
		d[k] = [v]
	else:
		d[k] += {v}
tmp = dict()
for i in range(line1[0] - 1):
	(p, c) = [int(x) for x in input().split(' ')]
	add_in_dict(tmp, p - 1, c - 1)
	add_in_dict(tmp, c - 1, p - 1)
visited = []
parents = [root]
while len(parents) > 0:
	current = parents.pop()
	ltmp = tmp.get(current)
	if ltmp is not None:
		for c in ltmp:
			if c not in visited:
				nodes[c].setParent(nodes[current])
				nodes[current].addChild(nodes[c])
				parents.append(c)
	visited.append(current)
for i in range(line1[1]):
	inp = input().split(' ')
	t = inp[0]
	integers = [int(x) for x in inp[1:]]
	if t == 'U':
		update(integers, nodes)
	else:
		print(query(integers, nodes, root + 1))


class Node(object):

	def __init__(self, value=0, parent=None):
		self.children = set()
		self.parent = parent
		self.value = value
		self.update = set()

	def addUpdate(self, arr):
		self.update.add((arr[0], arr[1]))

	def addChild(self, node):
		self.children.add(node)

	def setParent(self, node):
		self.parent = node

def root_path(bottom):
	chain = []
	while bottom is not None:
		chain.append(bottom)
		bottom = bottom.parent
	return chain

def height(bottom, top):
	res = 1
	while bottom != top and bottom is not None:
		bottom = bottom.parent
		res += 1
	return res

def q2(arr, nodes):
	(a, b) = arr
	first = nodes[a - 1]
	last = nodes[b - 1]
	path = root_path(last)
	h = height(last, first)
	res = 0
	while len(path) > 0:
		h = min(h, len(path))
		d = max(len(path) - h, 0)
		c = path.pop()
		for u in c.update:
			for i in range(h):
				res += (u[0] + (d + i) * u[1]) % (10 ** 9 + 7)
	return res % (10 ** 9 + 7)

def isRootBetween(bottom, top):
	if bottom == top:
		return False
	if bottom in root_path(top):
		return False
	if top in root_path(bottom):
		return False
	return True

def isDeeper(x, y):
	p = y
	while p is not None:
		if x == p:
			return False
		p = p.parent
	return True

def query(arr, nodes, root):
	(a, b) = arr
	x = nodes[a - 1]
	y = nodes[b - 1]
	if a == b == root:
		return q2([root, root], nodes)
	if isRootBetween(x, y):
		return (q2([root, a], nodes) + q2([root, b], nodes) - q2([root, root], nodes)) % (10 ** 9 + 7)
	elif isDeeper(x, y):
		return q2([b, a], nodes)
	else:
		return q2([a, b], nodes)

def update(arr, nodes):
	node = nodes[arr[0] - 1]
	node.addUpdate(arr[1:])
line1 = [int(x) for x in input().split(' ')]
nodes = [Node() for i in range(line1[0])]
root = line1[2] - 1

def add_in_dict(d, k, v):
	if d.get(k) is None:
		d[k] = [v]
	else:
		d[k] += {v}
tmp = dict()
for i in range(line1[0] - 1):
	(p, c) = [int(x) for x in input().split(' ')]
	add_in_dict(tmp, p - 1, c - 1)
	add_in_dict(tmp, c - 1, p - 1)
visited = []
parents = [root]
while len(parents) > 0:
	current = parents.pop()
	ltmp = tmp.get(current)
	if ltmp is not None:
		for c in ltmp:
			if c not in visited:
				nodes[c].setParent(nodes[current])
				nodes[current].addChild(nodes[c])
				parents.append(c)
	visited.append(current)
for i in range(line1[1]):
	inp = input().split(' ')
	t = inp[0]
	integers = [int(x) for x in inp[1:]]
	if t == 'U':
		update(integers, nodes)
	else:
		print(query(integers, nodes, root + 1))


class Node(object):

	def __init__(self, value=0, parent=None):
		self.children = set()
		self.parent = parent
		self.value = value
		self.update = set()

	def addUpdate(self, arr):
		self.update.add((arr[0], arr[1]))

	def addChild(self, node):
		self.children.add(node)

	def setParent(self, node):
		self.parent = node

def root_path(bottom):
	chain = []
	while bottom is not None:
		chain.append(bottom)
		bottom = bottom.parent
	return chain

def height(bottom, top):
	res = 1
	while bottom != top and bottom is not None:
		bottom = bottom.parent
		res += 1
	return res

def q2(arr, nodes):
	(a, b) = arr
	first = nodes[a - 1]
	last = nodes[b - 1]
	path = root_path(last)
	h = height(last, first)
	res = 0
	while len(path) > 0:
		h = min(h, len(path))
		d = max(len(path) - h, 0)
		c = path.pop()
		for u in c.update:
			for i in range(h):
				res += (u[0] + (d + i) * u[1]) % (10 ** 9 + 7)
	return res % (10 ** 9 + 7)

def isRootBetween(bottom, top):
	if bottom == top:
		return False
	if bottom in root_path(top):
		return False
	if top in root_path(bottom):
		return False
	return True

def isDeeper(x, y):
	p = y
	while p is not None:
		if x == p:
			return False
		p = p.parent
	return True

def query(arr, nodes, root):
	(a, b) = arr
	x = nodes[a - 1]
	y = nodes[b - 1]
	if a == b == root:
		return q2([root, root], nodes)
	if isRootBetween(x, y):
		return (q2([root, a], nodes) + q2([root, b], nodes) - q2([root, root], nodes)) % (10 ** 9 + 7)
	elif isDeeper(x, y):
		return q2([b, a], nodes)
	else:
		return q2([a, b], nodes)

def update(arr, nodes):
	node = nodes[arr[0] - 1]
	node.addUpdate(arr[1:])
line1 = [int(x) for x in input().split(' ')]
nodes = [Node() for i in range(line1[0])]
root = line1[2] - 1

def add_in_dict(d, k, v):
	if d.get(k) is None:
		d[k] = [v]
	else:
		d[k] += {v}
tmp = dict()
for i in range(line1[0] - 1):
	(p, c) = [int(x) for x in input().split(' ')]
	add_in_dict(tmp, p - 1, c - 1)
	add_in_dict(tmp, c - 1, p - 1)
visited = []
parents = [root]
while len(parents) > 0:
	current = parents.pop()
	ltmp = tmp.get(current)
	if ltmp is not None:
		for c in ltmp:
			if c not in visited:
				nodes[c].setParent(nodes[current])
				nodes[current].addChild(nodes[c])
				parents.append(c)
	visited.append(current)
for i in range(line1[1]):
	inp = input().split(' ')
	t = inp[0]
	integers = [int(x) for x in inp[1:]]
	if t == 'U':
		update(integers, nodes)
	else:
		print(query(integers, nodes, root + 1))


class Node(object):

	def __init__(self, value=0, parent=None):
		self.children = set()
		self.parent = parent
		self.value = value
		self.update = set()

	def addUpdate(self, arr):
		self.update.add((arr[0], arr[1]))

	def addChild(self, node):
		self.children.add(node)

	def setParent(self, node):
		self.parent = node

def root_path(bottom):
	chain = []
	while bottom is not None:
		chain.append(bottom)
		bottom = bottom.parent
	return chain

def height(bottom, top):
	res = 1
	while bottom != top and bottom is not None:
		bottom = bottom.parent
		res += 1
	return res

def q2(arr, nodes):
	(a, b) = arr
	first = nodes[a - 1]
	last = nodes[b - 1]
	path = root_path(last)
	h = height(last, first)
	res = 0
	while len(path) > 0:
		h = min(h, len(path))
		d = max(len(path) - h, 0)
		c = path.pop()
		for u in c.update:
			for i in range(h):
				res += (u[0] + (d + i) * u[1]) % (10 ** 9 + 7)
	return res % (10 ** 9 + 7)

def isRootBetween(bottom, top):
	if bottom == top:
		return False
	if bottom in root_path(top):
		return False
	if top in root_path(bottom):
		return False
	return True

def isDeeper(x, y):
	p = y
	while p is not None:
		if x == p:
			return False
		p = p.parent
	return True

def query(arr, nodes, root):
	(a, b) = arr
	x = nodes[a - 1]
	y = nodes[b - 1]
	if a == b == root:
		return q2([root, root], nodes)
	if isRootBetween(x, y):
		return (q2([root, a], nodes) + q2([root, b], nodes) - q2([root, root], nodes)) % (10 ** 9 + 7)
	elif isDeeper(x, y):
		return q2([b, a], nodes)
	else:
		return q2([a, b], nodes)

def update(arr, nodes):
	node = nodes[arr[0] - 1]
	node.addUpdate(arr[1:])
line1 = [int(x) for x in input().split(' ')]
nodes = [Node() for i in range(line1[0])]
root = line1[2] - 1

def add_in_dict(d, k, v):
	if d.get(k) is None:
		d[k] = [v]
	else:
		d[k] += {v}
tmp = dict()
for i in range(line1[0] - 1):
	(p, c) = [int(x) for x in input().split(' ')]
	add_in_dict(tmp, p - 1, c - 1)
	add_in_dict(tmp, c - 1, p - 1)
visited = []
parents = [root]
while len(parents) > 0:
	current = parents.pop()
	ltmp = tmp.get(current)
	if ltmp is not None:
		for c in ltmp:
			if c not in visited:
				nodes[c].setParent(nodes[current])
				nodes[current].addChild(nodes[c])
				parents.append(c)
	visited.append(current)
for i in range(line1[1]):
	inp = input().split(' ')
	t = inp[0]
	integers = [int(x) for x in inp[1:]]
	if t == 'U':
		update(integers, nodes)
	else:
		print(query(integers, nodes, root + 1))


class Node(object):

	def __init__(self, value=0, parent=None):
		self.children = set()
		self.parent = parent
		self.value = value
		self.update = set()

	def addUpdate(self, arr):
		self.update.add((arr[0], arr[1]))

	def addChild(self, node):
		self.children.add(node)

	def setParent(self, node):
		self.parent = node

def root_path(bottom):
	chain = []
	while bottom is not None:
		chain.append(bottom)
		bottom = bottom.parent
	return chain

def height(bottom, top):
	res = 1
	while bottom != top and bottom is not None:
		bottom = bottom.parent
		res += 1
	return res

def q2(arr, nodes):
	(a, b) = arr
	first = nodes[a - 1]
	last = nodes[b - 1]
	path = root_path(last)
	h = height(last, first)
	res = 0
	while len(path) > 0:
		h = min(h, len(path))
		d = max(len(path) - h, 0)
		c = path.pop()
		for u in c.update:
			for i in range(h):
				res += (u[0] + (d + i) * u[1]) % (10 ** 9 + 7)
	return res % (10 ** 9 + 7)

def isRootBetween(bottom, top):
	if bottom == top:
		return False
	if bottom in root_path(top):
		return False
	if top in root_path(bottom):
		return False
	return True

def isDeeper(x, y):
	p = y
	while p is not None:
		if x == p:
			return False
		p = p.parent
	return True

def query(arr, nodes, root):
	(a, b) = arr
	x = nodes[a - 1]
	y = nodes[b - 1]
	if a == b == root:
		return q2([root, root], nodes)
	if isRootBetween(x, y):
		return (q2([root, a], nodes) + q2([root, b], nodes) - q2([root, root], nodes)) % (10 ** 9 + 7)
	elif isDeeper(x, y):
		return q2([b, a], nodes)
	else:
		return q2([a, b], nodes)

def update(arr, nodes):
	node = nodes[arr[0] - 1]
	node.addUpdate(arr[1:])
line1 = [int(x) for x in input().split(' ')]
nodes = [Node() for i in range(line1[0])]
root = line1[2] - 1

def add_in_dict(d, k, v):
	if d.get(k) is None:
		d[k] = [v]
	else:
		d[k] += {v}
tmp = dict()
for i in range(line1[0] - 1):
	(p, c) = [int(x) for x in input().split(' ')]
	add_in_dict(tmp, p - 1, c - 1)
	add_in_dict(tmp, c - 1, p - 1)
visited = []
parents = [root]
while len(parents) > 0:
	current = parents.pop()
	ltmp = tmp.get(current)
	if ltmp is not None:
		for c in ltmp:
			if c not in visited:
				nodes[c].setParent(nodes[current])
				nodes[current].addChild(nodes[c])
				parents.append(c)
	visited.append(current)
for i in range(line1[1]):
	inp = input().split(' ')
	t = inp[0]
	integers = [int(x) for x in inp[1:]]
	if t == 'U':
		update(integers, nodes)
	else:
		print(query(integers, nodes, root + 1))


class Node(object):

	def __init__(self, value=0, parent=None):
		self.children = set()
		self.parent = parent
		self.value = value
		self.update = set()

	def addUpdate(self, arr):
		self.update.add((arr[0], arr[1]))

	def addChild(self, node):
		self.children.add(node)

	def setParent(self, node):
		self.parent = node

def root_path(bottom):
	chain = []
	while bottom is not None:
		chain.append(bottom)
		bottom = bottom.parent
	return chain

def height(bottom, top):
	res = 1
	while bottom != top and bottom is not None:
		bottom = bottom.parent
		res += 1
	return res

def q2(arr, nodes):
	(a, b) = arr
	first = nodes[a - 1]
	last = nodes[b - 1]
	path = root_path(last)
	h = height(last, first)
	res = 0
	while len(path) > 0:
		h = min(h, len(path))
		d = max(len(path) - h, 0)
		c = path.pop()
		for u in c.update:
			for i in range(h):
				res += (u[0] + (d + i) * u[1]) % (10 ** 9 + 7)
	return res % (10 ** 9 + 7)

def isRootBetween(bottom, top):
	if bottom == top:
		return False
	if bottom in root_path(top):
		return False
	if top in root_path(bottom):
		return False
	return True

def isDeeper(x, y):
	p = y
	while p is not None:
		if x == p:
			return False
		p = p.parent
	return True

def query(arr, nodes, root):
	(a, b) = arr
	x = nodes[a - 1]
	y = nodes[b - 1]
	if a == b == root:
		return q2([root, root], nodes)
	if isRootBetween(x, y):
		return (q2([root, a], nodes) + q2([root, b], nodes) - q2([root, root], nodes)) % (10 ** 9 + 7)
	elif isDeeper(x, y):
		return q2([b, a], nodes)
	else:
		return q2([a, b], nodes)

def update(arr, nodes):
	node = nodes[arr[0] - 1]
	node.addUpdate(arr[1:])
line1 = [int(x) for x in input().split(' ')]
nodes = [Node() for i in range(line1[0])]
root = line1[2] - 1

def add_in_dict(d, k, v):
	if d.get(k) is None:
		d[k] = [v]
	else:
		d[k] += {v}
tmp = dict()
for i in range(line1[0] - 1):
	(p, c) = [int(x) for x in input().split(' ')]
	add_in_dict(tmp, p - 1, c - 1)
	add_in_dict(tmp, c - 1, p - 1)
visited = []
parents = [root]
while len(parents) > 0:
	current = parents.pop()
	ltmp = tmp.get(current)
	if ltmp is not None:
		for c in ltmp:
			if c not in visited:
				nodes[c].setParent(nodes[current])
				nodes[current].addChild(nodes[c])
				parents.append(c)
	visited.append(current)
for i in range(line1[1]):
	inp = input().split(' ')
	t = inp[0]
	integers = [int(x) for x in inp[1:]]
	if t == 'U':
		update(integers, nodes)
	else:
		print(query(integers, nodes, root + 1))


class Node(object):

	def __init__(self, value=0, parent=None):
		self.children = set()
		self.parent = parent
		self.value = value
		self.update = set()

	def addUpdate(self, arr):
		self.update.add((arr[0], arr[1]))

	def addChild(self, node):
		self.children.add(node)

	def setParent(self, node):
		self.parent = node

def root_path(bottom):
	chain = []
	while bottom is not None:
		chain.append(bottom)
		bottom = bottom.parent
	return chain

def height(bottom, top):
	res = 1
	while bottom != top and bottom is not None:
		bottom = bottom.parent
		res += 1
	return res

def q2(arr, nodes):
	(a, b) = arr
	first = nodes[a - 1]
	last = nodes[b - 1]
	path = root_path(last)
	h = height(last, first)
	res = 0
	while len(path) > 0:
		h = min(h, len(path))
		d = max(len(path) - h, 0)
		c = path.pop()
		for u in c.update:
			for i in range(h):
				res += (u[0] + (d + i) * u[1]) % (10 ** 9 + 7)
	return res % (10 ** 9 + 7)

def isRootBetween(bottom, top):
	if bottom == top:
		return False
	if bottom in root_path(top):
		return False
	if top in root_path(bottom):
		return False
	return True

def isDeeper(x, y):
	p = y
	while p is not None:
		if x == p:
			return False
		p = p.parent
	return True

def query(arr, nodes, root):
	(a, b) = arr
	x = nodes[a - 1]
	y = nodes[b - 1]
	if a == b == root:
		return q2([root, root], nodes)
	if isRootBetween(x, y):
		return (q2([root, a], nodes) + q2([root, b], nodes) - q2([root, root], nodes)) % (10 ** 9 + 7)
	elif isDeeper(x, y):
		return q2([b, a], nodes)
	else:
		return q2([a, b], nodes)

def update(arr, nodes):
	node = nodes[arr[0] - 1]
	node.addUpdate(arr[1:])
line1 = [int(x) for x in input().split(' ')]
nodes = [Node() for i in range(line1[0])]
root = line1[2] - 1

def add_in_dict(d, k, v):
	if d.get(k) is None:
		d[k] = [v]
	else:
		d[k] += {v}
tmp = dict()
for i in range(line1[0] - 1):
	(p, c) = [int(x) for x in input().split(' ')]
	add_in_dict(tmp, p - 1, c - 1)
	add_in_dict(tmp, c - 1, p - 1)
visited = []
parents = [root]
while len(parents) > 0:
	current = parents.pop()
	ltmp = tmp.get(current)
	if ltmp is not None:
		for c in ltmp:
			if c not in visited:
				nodes[c].setParent(nodes[current])
				nodes[current].addChild(nodes[c])
				parents.append(c)
	visited.append(current)
for i in range(line1[1]):
	inp = input().split(' ')
	t = inp[0]
	integers = [int(x) for x in inp[1:]]
	if t == 'U':
		update(integers, nodes)
	else:
		print(query(integers, nodes, root + 1))


class Node(object):

	def __init__(self, value=0, parent=None):
		self.children = set()
		self.parent = parent
		self.value = value
		self.update = set()

	def addUpdate(self, arr):
		self.update.add((arr[0], arr[1]))

	def addChild(self, node):
		self.children.add(node)

	def setParent(self, node):
		self.parent = node

def root_path(bottom):
	chain = []
	while bottom is not None:
		chain.append(bottom)
		bottom = bottom.parent
	return chain

def height(bottom, top):
	res = 1
	while bottom != top and bottom is not None:
		bottom = bottom.parent
		res += 1
	return res

def q2(arr, nodes):
	(a, b) = arr
	first = nodes[a - 1]
	last = nodes[b - 1]
	path = root_path(last)
	h = height(last, first)
	res = 0
	while len(path) > 0:
		h = min(h, len(path))
		d = max(len(path) - h, 0)
		c = path.pop()
		for u in c.update:
			for i in range(h):
				res += (u[0] + (d + i) * u[1]) % (10 ** 9 + 7)
	return res % (10 ** 9 + 7)

def isRootBetween(bottom, top):
	if bottom == top:
		return False
	if bottom in root_path(top):
		return False
	if top in root_path(bottom):
		return False
	return True

def isDeeper(x, y):
	p = y
	while p is not None:
		if x == p:
			return False
		p = p.parent
	return True

def query(arr, nodes, root):
	(a, b) = arr
	x = nodes[a - 1]
	y = nodes[b - 1]
	if a == b == root:
		return q2([root, root], nodes)
	if isRootBetween(x, y):
		return (q2([root, a], nodes) + q2([root, b], nodes) - q2([root, root], nodes)) % (10 ** 9 + 7)
	elif isDeeper(x, y):
		return q2([b, a], nodes)
	else:
		return q2([a, b], nodes)

def update(arr, nodes):
	node = nodes[arr[0] - 1]
	node.addUpdate(arr[1:])
line1 = [int(x) for x in input().split(' ')]
nodes = [Node() for i in range(line1[0])]
root = line1[2] - 1

def add_in_dict(d, k, v):
	if d.get(k) is None:
		d[k] = [v]
	else:
		d[k] += {v}
tmp = dict()
for i in range(line1[0] - 1):
	(p, c) = [int(x) for x in input().split(' ')]
	add_in_dict(tmp, p - 1, c - 1)
	add_in_dict(tmp, c - 1, p - 1)
visited = []
parents = [root]
while len(parents) > 0:
	current = parents.pop()
	ltmp = tmp.get(current)
	if ltmp is not None:
		for c in ltmp:
			if c not in visited:
				nodes[c].setParent(nodes[current])
				nodes[current].addChild(nodes[c])
				parents.append(c)
	visited.append(current)
for i in range(line1[1]):
	inp = input().split(' ')
	t = inp[0]
	integers = [int(x) for x in inp[1:]]
	if t == 'U':
		update(integers, nodes)
	else:
		print(query(integers, nodes, root + 1))


class Node(object):

	def __init__(self, value=0, parent=None):
		self.children = set()
		self.parent = parent
		self.value = value
		self.update = set()

	def addUpdate(self, arr):
		self.update.add((arr[0], arr[1]))

	def addChild(self, node):
		self.children.add(node)

	def setParent(self, node):
		self.parent = node

def root_path(bottom):
	chain = []
	while bottom is not None:
		chain.append(bottom)
		bottom = bottom.parent
	return chain

def height(bottom, top):
	res = 1
	while bottom != top and bottom is not None:
		bottom = bottom.parent
		res += 1
	return res

def q2(arr, nodes):
	(a, b) = arr
	first = nodes[a - 1]
	last = nodes[b - 1]
	path = root_path(last)
	h = height(last, first)
	res = 0
	while len(path) > 0:
		h = min(h, len(path))
		d = max(len(path) - h, 0)
		c = path.pop()
		for u in c.update:
			for i in range(h):
				res += (u[0] + (d + i) * u[1]) % (10 ** 9 + 7)
	return res % (10 ** 9 + 7)

def isRootBetween(bottom, top):
	if bottom == top:
		return False
	if bottom in root_path(top):
		return False
	if top in root_path(bottom):
		return False
	return True

def isDeeper(x, y):
	p = y
	while p is not None:
		if x == p:
			return False
		p = p.parent
	return True

def query(arr, nodes, root):
	(a, b) = arr
	x = nodes[a - 1]
	y = nodes[b - 1]
	if a == b == root:
		return q2([root, root], nodes)
	if isRootBetween(x, y):
		return (q2([root, a], nodes) + q2([root, b], nodes) - q2([root, root], nodes)) % (10 ** 9 + 7)
	elif isDeeper(x, y):
		return q2([b, a], nodes)
	else:
		return q2([a, b], nodes)

def update(arr, nodes):
	node = nodes[arr[0] - 1]
	node.addUpdate(arr[1:])
line1 = [int(x) for x in input().split(' ')]
nodes = [Node() for i in range(line1[0])]
root = line1[2] - 1

def add_in_dict(d, k, v):
	if d.get(k) is None:
		d[k] = [v]
	else:
		d[k] += {v}
tmp = dict()
for i in range(line1[0] - 1):
	(p, c) = [int(x) for x in input().split(' ')]
	add_in_dict(tmp, p - 1, c - 1)
	add_in_dict(tmp, c - 1, p - 1)
visited = []
parents = [root]
while len(parents) > 0:
	current = parents.pop()
	ltmp = tmp.get(current)
	if ltmp is not None:
		for c in ltmp:
			if c not in visited:
				nodes[c].setParent(nodes[current])
				nodes[current].addChild(nodes[c])
				parents.append(c)
	visited.append(current)
for i in range(line1[1]):
	inp = input().split(' ')
	t = inp[0]
	integers = [int(x) for x in inp[1:]]
	if t == 'U':
		update(integers, nodes)
	else:
		print(query(integers, nodes, root + 1))


class Node(object):

	def __init__(self, value=0, parent=None):
		self.children = set()
		self.parent = parent
		self.value = value
		self.update = set()

	def addUpdate(self, arr):
		self.update.add((arr[0], arr[1]))

	def addChild(self, node):
		self.children.add(node)

	def setParent(self, node):
		self.parent = node

def root_path(bottom):
	chain = []
	while bottom is not None:
		chain.append(bottom)
		bottom = bottom.parent
	return chain

def height(bottom, top):
	res = 1
	while bottom != top and bottom is not None:
		bottom = bottom.parent
		res += 1
	return res

def q2(arr, nodes):
	(a, b) = arr
	first = nodes[a - 1]
	last = nodes[b - 1]
	path = root_path(last)
	h = height(last, first)
	res = 0
	while len(path) > 0:
		h = min(h, len(path))
		d = max(len(path) - h, 0)
		c = path.pop()
		for u in c.update:
			for i in range(h):
				res += (u[0] + (d + i) * u[1]) % (10 ** 9 + 7)
	return res % (10 ** 9 + 7)

def isRootBetween(bottom, top):
	if bottom == top:
		return False
	if bottom in root_path(top):
		return False
	if top in root_path(bottom):
		return False
	return True

def isDeeper(x, y):
	p = y
	while p is not None:
		if x == p:
			return False
		p = p.parent
	return True

def query(arr, nodes, root):
	(a, b) = arr
	x = nodes[a - 1]
	y = nodes[b - 1]
	if a == b == root:
		return q2([root, root], nodes)
	if isRootBetween(x, y):
		return (q2([root, a], nodes) + q2([root, b], nodes) - q2([root, root], nodes)) % (10 ** 9 + 7)
	elif isDeeper(x, y):
		return q2([b, a], nodes)
	else:
		return q2([a, b], nodes)

def update(arr, nodes):
	node = nodes[arr[0] - 1]
	node.addUpdate(arr[1:])
line1 = [int(x) for x in input().split(' ')]
nodes = [Node() for i in range(line1[0])]
root = line1[2] - 1

def add_in_dict(d, k, v):
	if d.get(k) is None:
		d[k] = [v]
	else:
		d[k] += {v}
tmp = dict()
for i in range(line1[0] - 1):
	(p, c) = [int(x) for x in input().split(' ')]
	add_in_dict(tmp, p - 1, c - 1)
	add_in_dict(tmp, c - 1, p - 1)
visited = []
parents = [root]
while len(parents) > 0:
	current = parents.pop()
	ltmp = tmp.get(current)
	if ltmp is not None:
		for c in ltmp:
			if c not in visited:
				nodes[c].setParent(nodes[current])
				nodes[current].addChild(nodes[c])
				parents.append(c)
	visited.append(current)
for i in range(line1[1]):
	inp = input().split(' ')
	t = inp[0]
	integers = [int(x) for x in inp[1:]]
	if t == 'U':
		update(integers, nodes)
	else:
		print(query(integers, nodes, root + 1))