Shashank loves trees and math. He has a rooted tree, $\mathbf{T}$, consisting of $N$ nodes uniquely labeled with integers in the inclusive range $[1,N]$. The node labeled as $1$ is the root node of tree $\mathbf{T}$, and each node in $\mathbf{T}$ is associated with some positive integer value (all values are initially $\mbox{0}$). 

Let's define $\mathbf{F_k}$ as the $k^{th}$ Fibonacci number. Shashank wants to perform $2$ types of operations over his tree, $\mathbf{T}$:

$\mbox{U}$ $\mbox{X}$ $\boldsymbol{\mbox{k}}$

Update the subtree rooted at node $\mbox{X}$ such that the node at level $0$ in subtree $\mbox{X}$ (i.e., node $\mbox{X}$) will have $\mathbf{F_k}$ added to it, all the nodes at level $\mbox{I}$ will have $\boldsymbol{F}_{k+1}$ added to them, and so on. More formally, all the nodes at a distance $\mbox{D}$ from node $\mbox{X}$ in the subtree of node $\mbox{X}$ will have the $(k+D)^{\mathrm{th}}$ Fibonacci number added to them.
$Q$ $\mbox{X}$ $\mathbf{Y}$

Find the sum of all values associated with the nodes on the unique path from $\mbox{X}$ to $\mathbf{Y}$. Print your sum modulo $10^9+7$ on a new line.

Given the configuration for tree $\mathbf{T}$ and a list of $\mbox{M}$ operations, perform all the operations efficiently.

Note: $F_1=F_2=1$.

Input Format

The first line contains $2$ space-separated integers, $N$ (the number of nodes in tree $\mathbf{T}$) and $\mbox{M}$ (the number of operations to be processed), respectively. 

Each line $\boldsymbol{i}$ of the $N-1$ subsequent lines contains an integer, $\mbox{P}$, denoting the parent of the $(i+1)^{th}$ node. 

Each of the $\mbox{M}$ subsequent lines contains one of the two types of operations mentioned in the Problem Statement above.

Constraints

$1\leq N,M\leq10^5$
$1\leq X,Y\leq N$
$1\leq k\leq10^{15}$

Output Format

For each operation of type $2$ (i.e., $Q$), print the required answer modulo $10^9+7$ on a new line.

Sample Input
5 10
1
1
2
2
Q 1 5
U 1 1
Q 1 1
Q 1 2
Q 1 3
Q 1 4
Q 1 5
U 2 2
Q 2 3
Q 4 5

Sample Output
0
1
2
2
4
4
4
10

Explanation

Intially, the tree looks like this:

After update operation $1\:\:1$, it looks like this:

After update operation $\textbf{2}\:\textbf{2}$, it looks like this:

Source: hackerrank | Difficulty: HARD
Tags: Data structures


Solutions:
mod = 10 ** 9 + 7
cache = {0: (0, 1), 1: (1, 1)}

def fib_pair(n):
	if n in cache:
		return cache[n]
	hn = n // 2
	(f, fp) = fib_pair(hn)
	if n & 1:
		res = ((fp * fp + f * f) % mod, (2 * f + fp) * fp % mod)
	else:
		fm = fp - f
		if fm < 0:
			fm += mod
		res = ((2 * fm + f) * f % mod, (fp * fp + f * f) % mod)
	if n < 1000000:
		cache[n] = res
	return res
(n, m) = map(int, input().strip().split())
parents = (n + 1) * [0]
children = [[] for _ in range(n + 1)]
for i in range(2, n + 1):
	j = int(input())
	parents[i] = j
	children[j].append(i)
depths = (n + 1) * [0]
stack = [(1, 1)]
while stack:
	(i, d) = stack.pop()
	depths[i] = d
	for j in children[i]:
		stack.append((j, d + 1))
nrs = (n + 1) * [0]
for _ in range(m):
	(q, si, sj) = input().strip().split()
	if q == 'U':
		(x, k) = (int(si), int(sj))
		fibs = list(fib_pair(k))
		stack = [(x, 0)]
		while stack:
			(y, l) = stack.pop()
			if l >= len(fibs):
				fibs.append((fibs[-1] + fibs[-2]) % mod)
			nrs[y] += fibs[l]
			for z in children[y]:
				stack.append((z, l + 1))
	else:
		(i, j) = (int(si), int(sj))
		if depths[i] < depths[j]:
			(i, j) = (j, i)
		fsum = 0
		while depths[j] < depths[i]:
			fsum += nrs[i]
			i = parents[i]
		while i != j:
			fsum += nrs[i] + nrs[j]
			j = parents[j]
			i = parents[i]
		fsum += nrs[i]
		print(fsum % mod)


class TreeNode:

	def __init__(self, node_id):
		self.node_id = node_id
		self.parent = None
		self.level = None
		self.children = []
		self.value = 0
		self.cumsum = 0

	def __repr__(self):
		return '%s(%s p=%s l=%d v=%d s=%d c=%d[%s])' % (self.__class__.__name__, self.node_id, self.parent.node_id if self.parent else '<>', self.level, self.value, self.cumsum, len(self.children), ' '.join((str(c.node_id) for c in self.children)))

	def print_recursive(self, level=0):
		print(level * ' ' + str(self))
		for c in self.children:
			c.print_recursive(level + 1)

	@classmethod
	def new(cls, node_id):
		node = cls(node_id)
		cls.tree[node_id] = node
		return node

	@classmethod
	def get(cls, node_id):
		try:
			return cls.tree[node_id] or cls.new(node_id)
		except KeyError:
			return cls.new(node_id)

	def set_root(self):
		if self.parent is not None:
			raise ValueError('TreeNode.set_root: already set', self)
		stack = [(self, None, 0)]
		while stack:
			(node, parent, level) = stack.pop()
			node.parent = parent
			node.level = level
			if level:
				node.children.remove(parent.node_id)
			for (i, c) in enumerate(node.children):
				node.children[i] = c = self.tree[c]
				stack.append((c, node, level + 1))

	@classmethod
	def common_parent(cls, n1, n2):
		if not isinstance(n1, TreeNode):
			n1 = cls.tree[n1]
		if not isinstance(n2, TreeNode):
			n2 = cls.tree[n2]
		if n1.level > n2.level:
			(n1, n2) = (n2, n1)
		while n2.level > n1.level:
			n2 = n2.parent
		while n1 != n2:
			n1 = n1.parent
			n2 = n2.parent
		return n1

	@classmethod
	def path_sum(cls, n1, n2):
		if not isinstance(n1, TreeNode):
			n1 = cls.tree[n1]
		if not isinstance(n2, TreeNode):
			n2 = cls.tree[n2]
		cr = cls.common_parent(n1, n2)
		if cr == n1:
			return n2.cumsum - n1.cumsum + n1.value
		if cr == n2:
			return n1.cumsum - n2.cumsum + n2.value
		return n1.cumsum + n2.cumsum - 2 * cr.cumsum + cr.value

	@classmethod
	def reduce_path(cls, init, func, nid1, nid2):
		n1 = cls.tree[nid1]
		n2 = cls.tree[nid2]
		if n1.level > n2.level:
			(n1, n2) = (n2, n1)
		curr = init
		while n2.level > n1.level:
			curr = func(curr, n2.value)
			n2 = n2.parent
		while n1 != n2:
			curr = func(func(curr, n1.value), n2.value)
			n1 = n1.parent
			n2 = n2.parent
		return func(curr, n1.value)
modulo_constant = 10 ** 9 + 7

def fibmod(n, mod=modulo_constant):
	if n == 0:
		return (0, 0)
	if n == 1:
		return (1, 0)
	if n == 2:
		return (1, 1)
	if n == 3:
		return (2, 1)
	if n == 4:
		return (3, 2)
	(f0, f1) = fibmod(n // 2, mod=mod)
	if n % 2:
		f2 = f0 + f1
		return ((f0 * f0 + f2 * f2) % mod, f0 * (f0 + f1 + f1) % mod)
	return (f0 * (f0 + f1 + f1) % mod, (f0 * f0 + f1 * f1) % mod)

class FibTree(TreeNode):
	tree = []

	def update(self, k):
		stack = [(self, fibmod(k), 0)]
		while stack:
			(node, (f1, f0), prev) = stack.pop()
			incr = f1
			node.value += incr
			prev += incr
			node.cumsum += prev
			f2 = (f0 + f1) % modulo_constant
			for c in node.children:
				stack.append((c, (f2, f1), prev))

	@classmethod
	def query(cls, nid1, nid2):
		return cls.path_sum(nid1, nid2) % modulo_constant

def read_queries(e, reader=input):
	queries = []
	for _ in range(e):
		q = reader().split()
		queries.append([q[0]] + [int(x) for x in q[1:]])
	return queries

def read_tree(nodes, cls, reader=input):
	cls.tree = [None] * (nodes + 1)
	for i in range(nodes - 1):
		nid = int(reader())
		cls.get(nid).children.append(i + 2)
		cls.get(i + 2).children.append(nid)
	cls.tree[1].set_root()

def read_problem(reader=input):
	(n, m) = map(int, reader().split())
	read_tree(n, FibTree, reader=reader)
	return read_queries(m, reader=reader)

def run_queries(queries):
	for (q, a, b) in queries:
		if q == 'U':
			FibTree.tree[a].update(b)
		elif q == 'Q':
			yield FibTree.query(a, b)
		else:
			raise ValueError('run_queries', q, a, b)
	return

def fib_tree(reader=input, printer=print):
	queries = read_problem(reader)
	for r in run_queries(queries):
		printer(str(r))
fib_tree()


mod = 10 ** 9 + 7
cache = {0: (0, 1), 1: (1, 1)}

def fib_pair(n):
	if n in cache:
		return cache[n]
	hn = n // 2
	(f, fp) = fib_pair(hn)
	if n & 1:
		res = ((fp * fp + f * f) % mod, (2 * f + fp) * fp % mod)
	else:
		fm = fp - f
		if fm < 0:
			fm += mod
		res = ((2 * fm + f) * f % mod, (fp * fp + f * f) % mod)
	if n < 1000000:
		cache[n] = res
	return res
(n, m) = map(int, input().strip().split())
parents = (n + 1) * [0]
children = [[] for _ in range(n + 1)]
for i in range(2, n + 1):
	j = int(input())
	parents[i] = j
	children[j].append(i)
depths = (n + 1) * [0]
stack = [(1, 1)]
while stack:
	(i, d) = stack.pop()
	depths[i] = d
	for j in children[i]:
		stack.append((j, d + 1))
nrs = (n + 1) * [0]
for _ in range(m):
	(q, si, sj) = input().strip().split()
	if q == 'U':
		(x, k) = (int(si), int(sj))
		fibs = list(fib_pair(k))
		stack = [(x, 0)]
		while stack:
			(y, l) = stack.pop()
			if l >= len(fibs):
				fibs.append((fibs[-1] + fibs[-2]) % mod)
			nrs[y] += fibs[l]
			for z in children[y]:
				stack.append((z, l + 1))
	else:
		(i, j) = (int(si), int(sj))
		if depths[i] < depths[j]:
			(i, j) = (j, i)
		fsum = 0
		while depths[j] < depths[i]:
			fsum += nrs[i]
			i = parents[i]
		while i != j:
			fsum += nrs[i] + nrs[j]
			j = parents[j]
			i = parents[i]
		fsum += nrs[i]
		print(fsum % mod)


mod = 10 ** 9 + 7
cache = {0: (0, 1), 1: (1, 1)}

def fib_pair(n):
	if n in cache:
		return cache[n]
	hn = n // 2
	(f, fp) = fib_pair(hn)
	if n & 1:
		res = ((fp * fp + f * f) % mod, (2 * f + fp) * fp % mod)
	else:
		fm = fp - f
		if fm < 0:
			fm += mod
		res = ((2 * fm + f) * f % mod, (fp * fp + f * f) % mod)
	if n < 1000000:
		cache[n] = res
	return res
(n, m) = map(int, input().strip().split())
parents = (n + 1) * [0]
children = [[] for _ in range(n + 1)]
for i in range(2, n + 1):
	j = int(input())
	parents[i] = j
	children[j].append(i)
depths = (n + 1) * [0]
stack = [(1, 1)]
while stack:
	(i, d) = stack.pop()
	depths[i] = d
	for j in children[i]:
		stack.append((j, d + 1))
nrs = (n + 1) * [0]
for _ in range(m):
	(q, si, sj) = input().strip().split()
	if q == 'U':
		(x, k) = (int(si), int(sj))
		fibs = list(fib_pair(k))
		stack = [(x, 0)]
		while stack:
			(y, l) = stack.pop()
			if l >= len(fibs):
				fibs.append((fibs[-1] + fibs[-2]) % mod)
			nrs[y] += fibs[l]
			for z in children[y]:
				stack.append((z, l + 1))
	else:
		(i, j) = (int(si), int(sj))
		if depths[i] < depths[j]:
			(i, j) = (j, i)
		fsum = 0
		while depths[j] < depths[i]:
			fsum += nrs[i]
			i = parents[i]
		while i != j:
			fsum += nrs[i] + nrs[j]
			j = parents[j]
			i = parents[i]
		fsum += nrs[i]
		print(fsum % mod)


mod = 10 ** 9 + 7
cache = {0: (0, 1), 1: (1, 1)}

def fib_pair(n):
	if n in cache:
		return cache[n]
	hn = n // 2
	(f, fp) = fib_pair(hn)
	if n & 1:
		res = ((fp * fp + f * f) % mod, (2 * f + fp) * fp % mod)
	else:
		fm = fp - f
		if fm < 0:
			fm += mod
		res = ((2 * fm + f) * f % mod, (fp * fp + f * f) % mod)
	if n < 1000000:
		cache[n] = res
	return res
(n, m) = map(int, input().strip().split())
parents = (n + 1) * [0]
children = [[] for _ in range(n + 1)]
for i in range(2, n + 1):
	j = int(input())
	parents[i] = j
	children[j].append(i)
depths = (n + 1) * [0]
stack = [(1, 1)]
while stack:
	(i, d) = stack.pop()
	depths[i] = d
	for j in children[i]:
		stack.append((j, d + 1))
nrs = (n + 1) * [0]
for _ in range(m):
	(q, si, sj) = input().strip().split()
	if q == 'U':
		(x, k) = (int(si), int(sj))
		fibs = list(fib_pair(k))
		stack = [(x, 0)]
		while stack:
			(y, l) = stack.pop()
			if l >= len(fibs):
				fibs.append((fibs[-1] + fibs[-2]) % mod)
			nrs[y] += fibs[l]
			for z in children[y]:
				stack.append((z, l + 1))
	else:
		(i, j) = (int(si), int(sj))
		if depths[i] < depths[j]:
			(i, j) = (j, i)
		fsum = 0
		while depths[j] < depths[i]:
			fsum += nrs[i]
			i = parents[i]
		while i != j:
			fsum += nrs[i] + nrs[j]
			j = parents[j]
			i = parents[i]
		fsum += nrs[i]
		print(fsum % mod)


mod = 10 ** 9 + 7
cache = {0: (0, 1), 1: (1, 1)}

def fib_pair(n):
	if n in cache:
		return cache[n]
	hn = n // 2
	(f, fp) = fib_pair(hn)
	if n & 1:
		res = ((fp * fp + f * f) % mod, (2 * f + fp) * fp % mod)
	else:
		fm = fp - f
		if fm < 0:
			fm += mod
		res = ((2 * fm + f) * f % mod, (fp * fp + f * f) % mod)
	if n < 1000000:
		cache[n] = res
	return res
(n, m) = map(int, input().strip().split())
parents = (n + 1) * [0]
children = [[] for _ in range(n + 1)]
for i in range(2, n + 1):
	j = int(input())
	parents[i] = j
	children[j].append(i)
depths = (n + 1) * [0]
stack = [(1, 1)]
while stack:
	(i, d) = stack.pop()
	depths[i] = d
	for j in children[i]:
		stack.append((j, d + 1))
nrs = (n + 1) * [0]
for _ in range(m):
	(q, si, sj) = input().strip().split()
	if q == 'U':
		(x, k) = (int(si), int(sj))
		fibs = list(fib_pair(k))
		stack = [(x, 0)]
		while stack:
			(y, l) = stack.pop()
			if l >= len(fibs):
				fibs.append((fibs[-1] + fibs[-2]) % mod)
			nrs[y] += fibs[l]
			for z in children[y]:
				stack.append((z, l + 1))
	else:
		(i, j) = (int(si), int(sj))
		if depths[i] < depths[j]:
			(i, j) = (j, i)
		fsum = 0
		while depths[j] < depths[i]:
			fsum += nrs[i]
			i = parents[i]
		while i != j:
			fsum += nrs[i] + nrs[j]
			j = parents[j]
			i = parents[i]
		fsum += nrs[i]
		print(fsum % mod)


mod = 10 ** 9 + 7
cache = {0: (0, 1), 1: (1, 1)}

def fib_pair(n):
	if n in cache:
		return cache[n]
	hn = n // 2
	(f, fp) = fib_pair(hn)
	if n & 1:
		res = ((fp * fp + f * f) % mod, (2 * f + fp) * fp % mod)
	else:
		fm = fp - f
		if fm < 0:
			fm += mod
		res = ((2 * fm + f) * f % mod, (fp * fp + f * f) % mod)
	if n < 1000000:
		cache[n] = res
	return res
(n, m) = map(int, input().strip().split())
parents = (n + 1) * [0]
children = [[] for _ in range(n + 1)]
for i in range(2, n + 1):
	j = int(input())
	parents[i] = j
	children[j].append(i)
depths = (n + 1) * [0]
stack = [(1, 1)]
while stack:
	(i, d) = stack.pop()
	depths[i] = d
	for j in children[i]:
		stack.append((j, d + 1))
nrs = (n + 1) * [0]
for _ in range(m):
	(q, si, sj) = input().strip().split()
	if q == 'U':
		(x, k) = (int(si), int(sj))
		fibs = list(fib_pair(k))
		stack = [(x, 0)]
		while stack:
			(y, l) = stack.pop()
			if l >= len(fibs):
				fibs.append((fibs[-1] + fibs[-2]) % mod)
			nrs[y] += fibs[l]
			for z in children[y]:
				stack.append((z, l + 1))
	else:
		(i, j) = (int(si), int(sj))
		if depths[i] < depths[j]:
			(i, j) = (j, i)
		fsum = 0
		while depths[j] < depths[i]:
			fsum += nrs[i]
			i = parents[i]
		while i != j:
			fsum += nrs[i] + nrs[j]
			j = parents[j]
			i = parents[i]
		fsum += nrs[i]
		print(fsum % mod)


mod = 10 ** 9 + 7
cache = {0: (0, 1), 1: (1, 1)}

def fib_pair(n):
	if n in cache:
		return cache[n]
	hn = n // 2
	(f, fp) = fib_pair(hn)
	if n & 1:
		res = ((fp * fp + f * f) % mod, (2 * f + fp) * fp % mod)
	else:
		fm = fp - f
		if fm < 0:
			fm += mod
		res = ((2 * fm + f) * f % mod, (fp * fp + f * f) % mod)
	if n < 1000000:
		cache[n] = res
	return res
(n, m) = map(int, input().strip().split())
parents = (n + 1) * [0]
children = [[] for _ in range(n + 1)]
for i in range(2, n + 1):
	j = int(input())
	parents[i] = j
	children[j].append(i)
depths = (n + 1) * [0]
stack = [(1, 1)]
while stack:
	(i, d) = stack.pop()
	depths[i] = d
	for j in children[i]:
		stack.append((j, d + 1))
nrs = (n + 1) * [0]
for _ in range(m):
	(q, si, sj) = input().strip().split()
	if q == 'U':
		(x, k) = (int(si), int(sj))
		fibs = list(fib_pair(k))
		stack = [(x, 0)]
		while stack:
			(y, l) = stack.pop()
			if l >= len(fibs):
				fibs.append((fibs[-1] + fibs[-2]) % mod)
			nrs[y] += fibs[l]
			for z in children[y]:
				stack.append((z, l + 1))
	else:
		(i, j) = (int(si), int(sj))
		if depths[i] < depths[j]:
			(i, j) = (j, i)
		fsum = 0
		while depths[j] < depths[i]:
			fsum += nrs[i]
			i = parents[i]
		while i != j:
			fsum += nrs[i] + nrs[j]
			j = parents[j]
			i = parents[i]
		fsum += nrs[i]
		print(fsum % mod)


mod = 10 ** 9 + 7
cache = {0: (0, 1), 1: (1, 1)}

def fib_pair(n):
	if n in cache:
		return cache[n]
	hn = n // 2
	(f, fp) = fib_pair(hn)
	if n & 1:
		res = ((fp * fp + f * f) % mod, (2 * f + fp) * fp % mod)
	else:
		fm = fp - f
		if fm < 0:
			fm += mod
		res = ((2 * fm + f) * f % mod, (fp * fp + f * f) % mod)
	if n < 1000000:
		cache[n] = res
	return res
(n, m) = map(int, input().strip().split())
parents = (n + 1) * [0]
children = [[] for _ in range(n + 1)]
for i in range(2, n + 1):
	j = int(input())
	parents[i] = j
	children[j].append(i)
depths = (n + 1) * [0]
stack = [(1, 1)]
while stack:
	(i, d) = stack.pop()
	depths[i] = d
	for j in children[i]:
		stack.append((j, d + 1))
nrs = (n + 1) * [0]
for _ in range(m):
	(q, si, sj) = input().strip().split()
	if q == 'U':
		(x, k) = (int(si), int(sj))
		fibs = list(fib_pair(k))
		stack = [(x, 0)]
		while stack:
			(y, l) = stack.pop()
			if l >= len(fibs):
				fibs.append((fibs[-1] + fibs[-2]) % mod)
			nrs[y] += fibs[l]
			for z in children[y]:
				stack.append((z, l + 1))
	else:
		(i, j) = (int(si), int(sj))
		if depths[i] < depths[j]:
			(i, j) = (j, i)
		fsum = 0
		while depths[j] < depths[i]:
			fsum += nrs[i]
			i = parents[i]
		while i != j:
			fsum += nrs[i] + nrs[j]
			j = parents[j]
			i = parents[i]
		fsum += nrs[i]
		print(fsum % mod)


mod = 10 ** 9 + 7
cache = {0: (0, 1), 1: (1, 1)}

def fib_pair(n):
	if n in cache:
		return cache[n]
	hn = n // 2
	(f, fp) = fib_pair(hn)
	if n & 1:
		res = ((fp * fp + f * f) % mod, (2 * f + fp) * fp % mod)
	else:
		fm = fp - f
		if fm < 0:
			fm += mod
		res = ((2 * fm + f) * f % mod, (fp * fp + f * f) % mod)
	if n < 1000000:
		cache[n] = res
	return res
(n, m) = map(int, input().strip().split())
parents = (n + 1) * [0]
children = [[] for _ in range(n + 1)]
for i in range(2, n + 1):
	j = int(input())
	parents[i] = j
	children[j].append(i)
depths = (n + 1) * [0]
stack = [(1, 1)]
while stack:
	(i, d) = stack.pop()
	depths[i] = d
	for j in children[i]:
		stack.append((j, d + 1))
nrs = (n + 1) * [0]
for _ in range(m):
	(q, si, sj) = input().strip().split()
	if q == 'U':
		(x, k) = (int(si), int(sj))
		fibs = list(fib_pair(k))
		stack = [(x, 0)]
		while stack:
			(y, l) = stack.pop()
			if l >= len(fibs):
				fibs.append((fibs[-1] + fibs[-2]) % mod)
			nrs[y] += fibs[l]
			for z in children[y]:
				stack.append((z, l + 1))
	else:
		(i, j) = (int(si), int(sj))
		if depths[i] < depths[j]:
			(i, j) = (j, i)
		fsum = 0
		while depths[j] < depths[i]:
			fsum += nrs[i]
			i = parents[i]
		while i != j:
			fsum += nrs[i] + nrs[j]
			j = parents[j]
			i = parents[i]
		fsum += nrs[i]
		print(fsum % mod)


mod = 10 ** 9 + 7
cache = {0: (0, 1), 1: (1, 1)}

def fib_pair(n):
	if n in cache:
		return cache[n]
	hn = n // 2
	(f, fp) = fib_pair(hn)
	if n & 1:
		res = ((fp * fp + f * f) % mod, (2 * f + fp) * fp % mod)
	else:
		fm = fp - f
		if fm < 0:
			fm += mod
		res = ((2 * fm + f) * f % mod, (fp * fp + f * f) % mod)
	if n < 1000000:
		cache[n] = res
	return res
(n, m) = map(int, input().strip().split())
parents = (n + 1) * [0]
children = [[] for _ in range(n + 1)]
for i in range(2, n + 1):
	j = int(input())
	parents[i] = j
	children[j].append(i)
depths = (n + 1) * [0]
stack = [(1, 1)]
while stack:
	(i, d) = stack.pop()
	depths[i] = d
	for j in children[i]:
		stack.append((j, d + 1))
nrs = (n + 1) * [0]
for _ in range(m):
	(q, si, sj) = input().strip().split()
	if q == 'U':
		(x, k) = (int(si), int(sj))
		fibs = list(fib_pair(k))
		stack = [(x, 0)]
		while stack:
			(y, l) = stack.pop()
			if l >= len(fibs):
				fibs.append((fibs[-1] + fibs[-2]) % mod)
			nrs[y] += fibs[l]
			for z in children[y]:
				stack.append((z, l + 1))
	else:
		(i, j) = (int(si), int(sj))
		if depths[i] < depths[j]:
			(i, j) = (j, i)
		fsum = 0
		while depths[j] < depths[i]:
			fsum += nrs[i]
			i = parents[i]
		while i != j:
			fsum += nrs[i] + nrs[j]
			j = parents[j]
			i = parents[i]
		fsum += nrs[i]
		print(fsum % mod)


mod = 10 ** 9 + 7
cache = {0: (0, 1), 1: (1, 1)}

def fib_pair(n):
	if n in cache:
		return cache[n]
	hn = n // 2
	(f, fp) = fib_pair(hn)
	if n & 1:
		res = ((fp * fp + f * f) % mod, (2 * f + fp) * fp % mod)
	else:
		fm = fp - f
		if fm < 0:
			fm += mod
		res = ((2 * fm + f) * f % mod, (fp * fp + f * f) % mod)
	if n < 1000000:
		cache[n] = res
	return res
(n, m) = map(int, input().strip().split())
parents = (n + 1) * [0]
children = [[] for _ in range(n + 1)]
for i in range(2, n + 1):
	j = int(input())
	parents[i] = j
	children[j].append(i)
depths = (n + 1) * [0]
stack = [(1, 1)]
while stack:
	(i, d) = stack.pop()
	depths[i] = d
	for j in children[i]:
		stack.append((j, d + 1))
nrs = (n + 1) * [0]
for _ in range(m):
	(q, si, sj) = input().strip().split()
	if q == 'U':
		(x, k) = (int(si), int(sj))
		fibs = list(fib_pair(k))
		stack = [(x, 0)]
		while stack:
			(y, l) = stack.pop()
			if l >= len(fibs):
				fibs.append((fibs[-1] + fibs[-2]) % mod)
			nrs[y] += fibs[l]
			for z in children[y]:
				stack.append((z, l + 1))
	else:
		(i, j) = (int(si), int(sj))
		if depths[i] < depths[j]:
			(i, j) = (j, i)
		fsum = 0
		while depths[j] < depths[i]:
			fsum += nrs[i]
			i = parents[i]
		while i != j:
			fsum += nrs[i] + nrs[j]
			j = parents[j]
			i = parents[i]
		fsum += nrs[i]
		print(fsum % mod)


mod = 10 ** 9 + 7
cache = {0: (0, 1), 1: (1, 1)}

def fib_pair(n):
	if n in cache:
		return cache[n]
	hn = n // 2
	(f, fp) = fib_pair(hn)
	if n & 1:
		res = ((fp * fp + f * f) % mod, (2 * f + fp) * fp % mod)
	else:
		fm = fp - f
		if fm < 0:
			fm += mod
		res = ((2 * fm + f) * f % mod, (fp * fp + f * f) % mod)
	if n < 1000000:
		cache[n] = res
	return res
(n, m) = map(int, input().strip().split())
parents = (n + 1) * [0]
children = [[] for _ in range(n + 1)]
for i in range(2, n + 1):
	j = int(input())
	parents[i] = j
	children[j].append(i)
depths = (n + 1) * [0]
stack = [(1, 1)]
while stack:
	(i, d) = stack.pop()
	depths[i] = d
	for j in children[i]:
		stack.append((j, d + 1))
nrs = (n + 1) * [0]
for _ in range(m):
	(q, si, sj) = input().strip().split()
	if q == 'U':
		(x, k) = (int(si), int(sj))
		fibs = list(fib_pair(k))
		stack = [(x, 0)]
		while stack:
			(y, l) = stack.pop()
			if l >= len(fibs):
				fibs.append((fibs[-1] + fibs[-2]) % mod)
			nrs[y] += fibs[l]
			for z in children[y]:
				stack.append((z, l + 1))
	else:
		(i, j) = (int(si), int(sj))
		if depths[i] < depths[j]:
			(i, j) = (j, i)
		fsum = 0
		while depths[j] < depths[i]:
			fsum += nrs[i]
			i = parents[i]
		while i != j:
			fsum += nrs[i] + nrs[j]
			j = parents[j]
			i = parents[i]
		fsum += nrs[i]
		print(fsum % mod)


mod = 10 ** 9 + 7
cache = {0: (0, 1), 1: (1, 1)}

def fib_pair(n):
	if n in cache:
		return cache[n]
	hn = n // 2
	(f, fp) = fib_pair(hn)
	if n & 1:
		res = ((fp * fp + f * f) % mod, (2 * f + fp) * fp % mod)
	else:
		fm = fp - f
		if fm < 0:
			fm += mod
		res = ((2 * fm + f) * f % mod, (fp * fp + f * f) % mod)
	if n < 1000000:
		cache[n] = res
	return res
(n, m) = map(int, input().strip().split())
parents = (n + 1) * [0]
children = [[] for _ in range(n + 1)]
for i in range(2, n + 1):
	j = int(input())
	parents[i] = j
	children[j].append(i)
depths = (n + 1) * [0]
stack = [(1, 1)]
while stack:
	(i, d) = stack.pop()
	depths[i] = d
	for j in children[i]:
		stack.append((j, d + 1))
nrs = (n + 1) * [0]
for _ in range(m):
	(q, si, sj) = input().strip().split()
	if q == 'U':
		(x, k) = (int(si), int(sj))
		fibs = list(fib_pair(k))
		stack = [(x, 0)]
		while stack:
			(y, l) = stack.pop()
			if l >= len(fibs):
				fibs.append((fibs[-1] + fibs[-2]) % mod)
			nrs[y] += fibs[l]
			for z in children[y]:
				stack.append((z, l + 1))
	else:
		(i, j) = (int(si), int(sj))
		if depths[i] < depths[j]:
			(i, j) = (j, i)
		fsum = 0
		while depths[j] < depths[i]:
			fsum += nrs[i]
			i = parents[i]
		while i != j:
			fsum += nrs[i] + nrs[j]
			j = parents[j]
			i = parents[i]
		fsum += nrs[i]
		print(fsum % mod)


mod = 10 ** 9 + 7
cache = {0: (0, 1), 1: (1, 1)}

def fib_pair(n):
	if n in cache:
		return cache[n]
	hn = n // 2
	(f, fp) = fib_pair(hn)
	if n & 1:
		res = ((fp * fp + f * f) % mod, (2 * f + fp) * fp % mod)
	else:
		fm = fp - f
		if fm < 0:
			fm += mod
		res = ((2 * fm + f) * f % mod, (fp * fp + f * f) % mod)
	if n < 1000000:
		cache[n] = res
	return res
(n, m) = map(int, input().strip().split())
parents = (n + 1) * [0]
children = [[] for _ in range(n + 1)]
for i in range(2, n + 1):
	j = int(input())
	parents[i] = j
	children[j].append(i)
depths = (n + 1) * [0]
stack = [(1, 1)]
while stack:
	(i, d) = stack.pop()
	depths[i] = d
	for j in children[i]:
		stack.append((j, d + 1))
nrs = (n + 1) * [0]
for _ in range(m):
	(q, si, sj) = input().strip().split()
	if q == 'U':
		(x, k) = (int(si), int(sj))
		fibs = list(fib_pair(k))
		stack = [(x, 0)]
		while stack:
			(y, l) = stack.pop()
			if l >= len(fibs):
				fibs.append((fibs[-1] + fibs[-2]) % mod)
			nrs[y] += fibs[l]
			for z in children[y]:
				stack.append((z, l + 1))
	else:
		(i, j) = (int(si), int(sj))
		if depths[i] < depths[j]:
			(i, j) = (j, i)
		fsum = 0
		while depths[j] < depths[i]:
			fsum += nrs[i]
			i = parents[i]
		while i != j:
			fsum += nrs[i] + nrs[j]
			j = parents[j]
			i = parents[i]
		fsum += nrs[i]
		print(fsum % mod)


mod = 10 ** 9 + 7
cache = {0: (0, 1), 1: (1, 1)}

def fib_pair(n):
	if n in cache:
		return cache[n]
	hn = n // 2
	(f, fp) = fib_pair(hn)
	if n & 1:
		res = ((fp * fp + f * f) % mod, (2 * f + fp) * fp % mod)
	else:
		fm = fp - f
		if fm < 0:
			fm += mod
		res = ((2 * fm + f) * f % mod, (fp * fp + f * f) % mod)
	if n < 1000000:
		cache[n] = res
	return res
(n, m) = map(int, input().strip().split())
parents = (n + 1) * [0]
children = [[] for _ in range(n + 1)]
for i in range(2, n + 1):
	j = int(input())
	parents[i] = j
	children[j].append(i)
depths = (n + 1) * [0]
stack = [(1, 1)]
while stack:
	(i, d) = stack.pop()
	depths[i] = d
	for j in children[i]:
		stack.append((j, d + 1))
nrs = (n + 1) * [0]
for _ in range(m):
	(q, si, sj) = input().strip().split()
	if q == 'U':
		(x, k) = (int(si), int(sj))
		fibs = list(fib_pair(k))
		stack = [(x, 0)]
		while stack:
			(y, l) = stack.pop()
			if l >= len(fibs):
				fibs.append((fibs[-1] + fibs[-2]) % mod)
			nrs[y] += fibs[l]
			for z in children[y]:
				stack.append((z, l + 1))
	else:
		(i, j) = (int(si), int(sj))
		if depths[i] < depths[j]:
			(i, j) = (j, i)
		fsum = 0
		while depths[j] < depths[i]:
			fsum += nrs[i]
			i = parents[i]
		while i != j:
			fsum += nrs[i] + nrs[j]
			j = parents[j]
			i = parents[i]
		fsum += nrs[i]
		print(fsum % mod)


mod = 10 ** 9 + 7
cache = {0: (0, 1), 1: (1, 1)}

def fib_pair(n):
	if n in cache:
		return cache[n]
	hn = n // 2
	(f, fp) = fib_pair(hn)
	if n & 1:
		res = ((fp * fp + f * f) % mod, (2 * f + fp) * fp % mod)
	else:
		fm = fp - f
		if fm < 0:
			fm += mod
		res = ((2 * fm + f) * f % mod, (fp * fp + f * f) % mod)
	if n < 1000000:
		cache[n] = res
	return res
(n, m) = map(int, input().strip().split())
parents = (n + 1) * [0]
children = [[] for _ in range(n + 1)]
for i in range(2, n + 1):
	j = int(input())
	parents[i] = j
	children[j].append(i)
depths = (n + 1) * [0]
stack = [(1, 1)]
while stack:
	(i, d) = stack.pop()
	depths[i] = d
	for j in children[i]:
		stack.append((j, d + 1))
nrs = (n + 1) * [0]
for _ in range(m):
	(q, si, sj) = input().strip().split()
	if q == 'U':
		(x, k) = (int(si), int(sj))
		fibs = list(fib_pair(k))
		stack = [(x, 0)]
		while stack:
			(y, l) = stack.pop()
			if l >= len(fibs):
				fibs.append((fibs[-1] + fibs[-2]) % mod)
			nrs[y] += fibs[l]
			for z in children[y]:
				stack.append((z, l + 1))
	else:
		(i, j) = (int(si), int(sj))
		if depths[i] < depths[j]:
			(i, j) = (j, i)
		fsum = 0
		while depths[j] < depths[i]:
			fsum += nrs[i]
			i = parents[i]
		while i != j:
			fsum += nrs[i] + nrs[j]
			j = parents[j]
			i = parents[i]
		fsum += nrs[i]
		print(fsum % mod)


mod = 10 ** 9 + 7
cache = {0: (0, 1), 1: (1, 1)}

def fib_pair(n):
	if n in cache:
		return cache[n]
	hn = n // 2
	(f, fp) = fib_pair(hn)
	if n & 1:
		res = ((fp * fp + f * f) % mod, (2 * f + fp) * fp % mod)
	else:
		fm = fp - f
		if fm < 0:
			fm += mod
		res = ((2 * fm + f) * f % mod, (fp * fp + f * f) % mod)
	if n < 1000000:
		cache[n] = res
	return res
(n, m) = map(int, input().strip().split())
parents = (n + 1) * [0]
children = [[] for _ in range(n + 1)]
for i in range(2, n + 1):
	j = int(input())
	parents[i] = j
	children[j].append(i)
depths = (n + 1) * [0]
stack = [(1, 1)]
while stack:
	(i, d) = stack.pop()
	depths[i] = d
	for j in children[i]:
		stack.append((j, d + 1))
nrs = (n + 1) * [0]
for _ in range(m):
	(q, si, sj) = input().strip().split()
	if q == 'U':
		(x, k) = (int(si), int(sj))
		fibs = list(fib_pair(k))
		stack = [(x, 0)]
		while stack:
			(y, l) = stack.pop()
			if l >= len(fibs):
				fibs.append((fibs[-1] + fibs[-2]) % mod)
			nrs[y] += fibs[l]
			for z in children[y]:
				stack.append((z, l + 1))
	else:
		(i, j) = (int(si), int(sj))
		if depths[i] < depths[j]:
			(i, j) = (j, i)
		fsum = 0
		while depths[j] < depths[i]:
			fsum += nrs[i]
			i = parents[i]
		while i != j:
			fsum += nrs[i] + nrs[j]
			j = parents[j]
			i = parents[i]
		fsum += nrs[i]
		print(fsum % mod)


mod = 10 ** 9 + 7
cache = {0: (0, 1), 1: (1, 1)}

def fib_pair(n):
	if n in cache:
		return cache[n]
	hn = n // 2
	(f, fp) = fib_pair(hn)
	if n & 1:
		res = ((fp * fp + f * f) % mod, (2 * f + fp) * fp % mod)
	else:
		fm = fp - f
		if fm < 0:
			fm += mod
		res = ((2 * fm + f) * f % mod, (fp * fp + f * f) % mod)
	if n < 1000000:
		cache[n] = res
	return res
(n, m) = map(int, input().strip().split())
parents = (n + 1) * [0]
children = [[] for _ in range(n + 1)]
for i in range(2, n + 1):
	j = int(input())
	parents[i] = j
	children[j].append(i)
depths = (n + 1) * [0]
stack = [(1, 1)]
while stack:
	(i, d) = stack.pop()
	depths[i] = d
	for j in children[i]:
		stack.append((j, d + 1))
nrs = (n + 1) * [0]
for _ in range(m):
	(q, si, sj) = input().strip().split()
	if q == 'U':
		(x, k) = (int(si), int(sj))
		fibs = list(fib_pair(k))
		stack = [(x, 0)]
		while stack:
			(y, l) = stack.pop()
			if l >= len(fibs):
				fibs.append((fibs[-1] + fibs[-2]) % mod)
			nrs[y] += fibs[l]
			for z in children[y]:
				stack.append((z, l + 1))
	else:
		(i, j) = (int(si), int(sj))
		if depths[i] < depths[j]:
			(i, j) = (j, i)
		fsum = 0
		while depths[j] < depths[i]:
			fsum += nrs[i]
			i = parents[i]
		while i != j:
			fsum += nrs[i] + nrs[j]
			j = parents[j]
			i = parents[i]
		fsum += nrs[i]
		print(fsum % mod)


mod = 10 ** 9 + 7
cache = {0: (0, 1), 1: (1, 1)}

def fib_pair(n):
	if n in cache:
		return cache[n]
	hn = n // 2
	(f, fp) = fib_pair(hn)
	if n & 1:
		res = ((fp * fp + f * f) % mod, (2 * f + fp) * fp % mod)
	else:
		fm = fp - f
		if fm < 0:
			fm += mod
		res = ((2 * fm + f) * f % mod, (fp * fp + f * f) % mod)
	if n < 1000000:
		cache[n] = res
	return res
(n, m) = map(int, input().strip().split())
parents = (n + 1) * [0]
children = [[] for _ in range(n + 1)]
for i in range(2, n + 1):
	j = int(input())
	parents[i] = j
	children[j].append(i)
depths = (n + 1) * [0]
stack = [(1, 1)]
while stack:
	(i, d) = stack.pop()
	depths[i] = d
	for j in children[i]:
		stack.append((j, d + 1))
nrs = (n + 1) * [0]
for _ in range(m):
	(q, si, sj) = input().strip().split()
	if q == 'U':
		(x, k) = (int(si), int(sj))
		fibs = list(fib_pair(k))
		stack = [(x, 0)]
		while stack:
			(y, l) = stack.pop()
			if l >= len(fibs):
				fibs.append((fibs[-1] + fibs[-2]) % mod)
			nrs[y] += fibs[l]
			for z in children[y]:
				stack.append((z, l + 1))
	else:
		(i, j) = (int(si), int(sj))
		if depths[i] < depths[j]:
			(i, j) = (j, i)
		fsum = 0
		while depths[j] < depths[i]:
			fsum += nrs[i]
			i = parents[i]
		while i != j:
			fsum += nrs[i] + nrs[j]
			j = parents[j]
			i = parents[i]
		fsum += nrs[i]
		print(fsum % mod)


mod = 10 ** 9 + 7
cache = {0: (0, 1), 1: (1, 1)}

def fib_pair(n):
	if n in cache:
		return cache[n]
	hn = n // 2
	(f, fp) = fib_pair(hn)
	if n & 1:
		res = ((fp * fp + f * f) % mod, (2 * f + fp) * fp % mod)
	else:
		fm = fp - f
		if fm < 0:
			fm += mod
		res = ((2 * fm + f) * f % mod, (fp * fp + f * f) % mod)
	if n < 1000000:
		cache[n] = res
	return res
(n, m) = map(int, input().strip().split())
parents = (n + 1) * [0]
children = [[] for _ in range(n + 1)]
for i in range(2, n + 1):
	j = int(input())
	parents[i] = j
	children[j].append(i)
depths = (n + 1) * [0]
stack = [(1, 1)]
while stack:
	(i, d) = stack.pop()
	depths[i] = d
	for j in children[i]:
		stack.append((j, d + 1))
nrs = (n + 1) * [0]
for _ in range(m):
	(q, si, sj) = input().strip().split()
	if q == 'U':
		(x, k) = (int(si), int(sj))
		fibs = list(fib_pair(k))
		stack = [(x, 0)]
		while stack:
			(y, l) = stack.pop()
			if l >= len(fibs):
				fibs.append((fibs[-1] + fibs[-2]) % mod)
			nrs[y] += fibs[l]
			for z in children[y]:
				stack.append((z, l + 1))
	else:
		(i, j) = (int(si), int(sj))
		if depths[i] < depths[j]:
			(i, j) = (j, i)
		fsum = 0
		while depths[j] < depths[i]:
			fsum += nrs[i]
			i = parents[i]
		while i != j:
			fsum += nrs[i] + nrs[j]
			j = parents[j]
			i = parents[i]
		fsum += nrs[i]
		print(fsum % mod)


mod = 10 ** 9 + 7
cache = {0: (0, 1), 1: (1, 1)}

def fib_pair(n):
	if n in cache:
		return cache[n]
	hn = n // 2
	(f, fp) = fib_pair(hn)
	if n & 1:
		res = ((fp * fp + f * f) % mod, (2 * f + fp) * fp % mod)
	else:
		fm = fp - f
		if fm < 0:
			fm += mod
		res = ((2 * fm + f) * f % mod, (fp * fp + f * f) % mod)
	if n < 1000000:
		cache[n] = res
	return res
(n, m) = map(int, input().strip().split())
parents = (n + 1) * [0]
children = [[] for _ in range(n + 1)]
for i in range(2, n + 1):
	j = int(input())
	parents[i] = j
	children[j].append(i)
depths = (n + 1) * [0]
stack = [(1, 1)]
while stack:
	(i, d) = stack.pop()
	depths[i] = d
	for j in children[i]:
		stack.append((j, d + 1))
nrs = (n + 1) * [0]
for _ in range(m):
	(q, si, sj) = input().strip().split()
	if q == 'U':
		(x, k) = (int(si), int(sj))
		fibs = list(fib_pair(k))
		stack = [(x, 0)]
		while stack:
			(y, l) = stack.pop()
			if l >= len(fibs):
				fibs.append((fibs[-1] + fibs[-2]) % mod)
			nrs[y] += fibs[l]
			for z in children[y]:
				stack.append((z, l + 1))
	else:
		(i, j) = (int(si), int(sj))
		if depths[i] < depths[j]:
			(i, j) = (j, i)
		fsum = 0
		while depths[j] < depths[i]:
			fsum += nrs[i]
			i = parents[i]
		while i != j:
			fsum += nrs[i] + nrs[j]
			j = parents[j]
			i = parents[i]
		fsum += nrs[i]
		print(fsum % mod)


mod = 10 ** 9 + 7
cache = {0: (0, 1), 1: (1, 1)}

def fib_pair(n):
	if n in cache:
		return cache[n]
	hn = n // 2
	(f, fp) = fib_pair(hn)
	if n & 1:
		res = ((fp * fp + f * f) % mod, (2 * f + fp) * fp % mod)
	else:
		fm = fp - f
		if fm < 0:
			fm += mod
		res = ((2 * fm + f) * f % mod, (fp * fp + f * f) % mod)
	if n < 1000000:
		cache[n] = res
	return res
(n, m) = map(int, input().strip().split())
parents = (n + 1) * [0]
children = [[] for _ in range(n + 1)]
for i in range(2, n + 1):
	j = int(input())
	parents[i] = j
	children[j].append(i)
depths = (n + 1) * [0]
stack = [(1, 1)]
while stack:
	(i, d) = stack.pop()
	depths[i] = d
	for j in children[i]:
		stack.append((j, d + 1))
nrs = (n + 1) * [0]
for _ in range(m):
	(q, si, sj) = input().strip().split()
	if q == 'U':
		(x, k) = (int(si), int(sj))
		fibs = list(fib_pair(k))
		stack = [(x, 0)]
		while stack:
			(y, l) = stack.pop()
			if l >= len(fibs):
				fibs.append((fibs[-1] + fibs[-2]) % mod)
			nrs[y] += fibs[l]
			for z in children[y]:
				stack.append((z, l + 1))
	else:
		(i, j) = (int(si), int(sj))
		if depths[i] < depths[j]:
			(i, j) = (j, i)
		fsum = 0
		while depths[j] < depths[i]:
			fsum += nrs[i]
			i = parents[i]
		while i != j:
			fsum += nrs[i] + nrs[j]
			j = parents[j]
			i = parents[i]
		fsum += nrs[i]
		print(fsum % mod)


mod = 10 ** 9 + 7
cache = {0: (0, 1), 1: (1, 1)}

def fib_pair(n):
	if n in cache:
		return cache[n]
	hn = n // 2
	(f, fp) = fib_pair(hn)
	if n & 1:
		res = ((fp * fp + f * f) % mod, (2 * f + fp) * fp % mod)
	else:
		fm = fp - f
		if fm < 0:
			fm += mod
		res = ((2 * fm + f) * f % mod, (fp * fp + f * f) % mod)
	if n < 1000000:
		cache[n] = res
	return res
(n, m) = map(int, input().strip().split())
parents = (n + 1) * [0]
children = [[] for _ in range(n + 1)]
for i in range(2, n + 1):
	j = int(input())
	parents[i] = j
	children[j].append(i)
depths = (n + 1) * [0]
stack = [(1, 1)]
while stack:
	(i, d) = stack.pop()
	depths[i] = d
	for j in children[i]:
		stack.append((j, d + 1))
nrs = (n + 1) * [0]
for _ in range(m):
	(q, si, sj) = input().strip().split()
	if q == 'U':
		(x, k) = (int(si), int(sj))
		fibs = list(fib_pair(k))
		stack = [(x, 0)]
		while stack:
			(y, l) = stack.pop()
			if l >= len(fibs):
				fibs.append((fibs[-1] + fibs[-2]) % mod)
			nrs[y] += fibs[l]
			for z in children[y]:
				stack.append((z, l + 1))
	else:
		(i, j) = (int(si), int(sj))
		if depths[i] < depths[j]:
			(i, j) = (j, i)
		fsum = 0
		while depths[j] < depths[i]:
			fsum += nrs[i]
			i = parents[i]
		while i != j:
			fsum += nrs[i] + nrs[j]
			j = parents[j]
			i = parents[i]
		fsum += nrs[i]
		print(fsum % mod)


mod = 10 ** 9 + 7
cache = {0: (0, 1), 1: (1, 1)}

def fib_pair(n):
	if n in cache:
		return cache[n]
	hn = n // 2
	(f, fp) = fib_pair(hn)
	if n & 1:
		res = ((fp * fp + f * f) % mod, (2 * f + fp) * fp % mod)
	else:
		fm = fp - f
		if fm < 0:
			fm += mod
		res = ((2 * fm + f) * f % mod, (fp * fp + f * f) % mod)
	if n < 1000000:
		cache[n] = res
	return res
(n, m) = map(int, input().strip().split())
parents = (n + 1) * [0]
children = [[] for _ in range(n + 1)]
for i in range(2, n + 1):
	j = int(input())
	parents[i] = j
	children[j].append(i)
depths = (n + 1) * [0]
stack = [(1, 1)]
while stack:
	(i, d) = stack.pop()
	depths[i] = d
	for j in children[i]:
		stack.append((j, d + 1))
nrs = (n + 1) * [0]
for _ in range(m):
	(q, si, sj) = input().strip().split()
	if q == 'U':
		(x, k) = (int(si), int(sj))
		fibs = list(fib_pair(k))
		stack = [(x, 0)]
		while stack:
			(y, l) = stack.pop()
			if l >= len(fibs):
				fibs.append((fibs[-1] + fibs[-2]) % mod)
			nrs[y] += fibs[l]
			for z in children[y]:
				stack.append((z, l + 1))
	else:
		(i, j) = (int(si), int(sj))
		if depths[i] < depths[j]:
			(i, j) = (j, i)
		fsum = 0
		while depths[j] < depths[i]:
			fsum += nrs[i]
			i = parents[i]
		while i != j:
			fsum += nrs[i] + nrs[j]
			j = parents[j]
			i = parents[i]
		fsum += nrs[i]
		print(fsum % mod)


mod = 10 ** 9 + 7
cache = {0: (0, 1), 1: (1, 1)}

def fib_pair(n):
	if n in cache:
		return cache[n]
	hn = n // 2
	(f, fp) = fib_pair(hn)
	if n & 1:
		res = ((fp * fp + f * f) % mod, (2 * f + fp) * fp % mod)
	else:
		fm = fp - f
		if fm < 0:
			fm += mod
		res = ((2 * fm + f) * f % mod, (fp * fp + f * f) % mod)
	if n < 1000000:
		cache[n] = res
	return res
(n, m) = map(int, input().strip().split())
parents = (n + 1) * [0]
children = [[] for _ in range(n + 1)]
for i in range(2, n + 1):
	j = int(input())
	parents[i] = j
	children[j].append(i)
depths = (n + 1) * [0]
stack = [(1, 1)]
while stack:
	(i, d) = stack.pop()
	depths[i] = d
	for j in children[i]:
		stack.append((j, d + 1))
nrs = (n + 1) * [0]
for _ in range(m):
	(q, si, sj) = input().strip().split()
	if q == 'U':
		(x, k) = (int(si), int(sj))
		fibs = list(fib_pair(k))
		stack = [(x, 0)]
		while stack:
			(y, l) = stack.pop()
			if l >= len(fibs):
				fibs.append((fibs[-1] + fibs[-2]) % mod)
			nrs[y] += fibs[l]
			for z in children[y]:
				stack.append((z, l + 1))
	else:
		(i, j) = (int(si), int(sj))
		if depths[i] < depths[j]:
			(i, j) = (j, i)
		fsum = 0
		while depths[j] < depths[i]:
			fsum += nrs[i]
			i = parents[i]
		while i != j:
			fsum += nrs[i] + nrs[j]
			j = parents[j]
			i = parents[i]
		fsum += nrs[i]
		print(fsum % mod)


mod = 10 ** 9 + 7
cache = {0: (0, 1), 1: (1, 1)}

def fib_pair(n):
	if n in cache:
		return cache[n]
	hn = n // 2
	(f, fp) = fib_pair(hn)
	if n & 1:
		res = ((fp * fp + f * f) % mod, (2 * f + fp) * fp % mod)
	else:
		fm = fp - f
		if fm < 0:
			fm += mod
		res = ((2 * fm + f) * f % mod, (fp * fp + f * f) % mod)
	if n < 1000000:
		cache[n] = res
	return res
(n, m) = map(int, input().strip().split())
parents = (n + 1) * [0]
children = [[] for _ in range(n + 1)]
for i in range(2, n + 1):
	j = int(input())
	parents[i] = j
	children[j].append(i)
depths = (n + 1) * [0]
stack = [(1, 1)]
while stack:
	(i, d) = stack.pop()
	depths[i] = d
	for j in children[i]:
		stack.append((j, d + 1))
nrs = (n + 1) * [0]
for _ in range(m):
	(q, si, sj) = input().strip().split()
	if q == 'U':
		(x, k) = (int(si), int(sj))
		fibs = list(fib_pair(k))
		stack = [(x, 0)]
		while stack:
			(y, l) = stack.pop()
			if l >= len(fibs):
				fibs.append((fibs[-1] + fibs[-2]) % mod)
			nrs[y] += fibs[l]
			for z in children[y]:
				stack.append((z, l + 1))
	else:
		(i, j) = (int(si), int(sj))
		if depths[i] < depths[j]:
			(i, j) = (j, i)
		fsum = 0
		while depths[j] < depths[i]:
			fsum += nrs[i]
			i = parents[i]
		while i != j:
			fsum += nrs[i] + nrs[j]
			j = parents[j]
			i = parents[i]
		fsum += nrs[i]
		print(fsum % mod)


mod = 10 ** 9 + 7
cache = {0: (0, 1), 1: (1, 1)}

def fib_pair(n):
	if n in cache:
		return cache[n]
	hn = n // 2
	(f, fp) = fib_pair(hn)
	if n & 1:
		res = ((fp * fp + f * f) % mod, (2 * f + fp) * fp % mod)
	else:
		fm = fp - f
		if fm < 0:
			fm += mod
		res = ((2 * fm + f) * f % mod, (fp * fp + f * f) % mod)
	if n < 1000000:
		cache[n] = res
	return res
(n, m) = map(int, input().strip().split())
parents = (n + 1) * [0]
children = [[] for _ in range(n + 1)]
for i in range(2, n + 1):
	j = int(input())
	parents[i] = j
	children[j].append(i)
depths = (n + 1) * [0]
stack = [(1, 1)]
while stack:
	(i, d) = stack.pop()
	depths[i] = d
	for j in children[i]:
		stack.append((j, d + 1))
nrs = (n + 1) * [0]
for _ in range(m):
	(q, si, sj) = input().strip().split()
	if q == 'U':
		(x, k) = (int(si), int(sj))
		fibs = list(fib_pair(k))
		stack = [(x, 0)]
		while stack:
			(y, l) = stack.pop()
			if l >= len(fibs):
				fibs.append((fibs[-1] + fibs[-2]) % mod)
			nrs[y] += fibs[l]
			for z in children[y]:
				stack.append((z, l + 1))
	else:
		(i, j) = (int(si), int(sj))
		if depths[i] < depths[j]:
			(i, j) = (j, i)
		fsum = 0
		while depths[j] < depths[i]:
			fsum += nrs[i]
			i = parents[i]
		while i != j:
			fsum += nrs[i] + nrs[j]
			j = parents[j]
			i = parents[i]
		fsum += nrs[i]
		print(fsum % mod)


mod = 10 ** 9 + 7
cache = {0: (0, 1), 1: (1, 1)}

def fib_pair(n):
	if n in cache:
		return cache[n]
	hn = n // 2
	(f, fp) = fib_pair(hn)
	if n & 1:
		res = ((fp * fp + f * f) % mod, (2 * f + fp) * fp % mod)
	else:
		fm = fp - f
		if fm < 0:
			fm += mod
		res = ((2 * fm + f) * f % mod, (fp * fp + f * f) % mod)
	if n < 1000000:
		cache[n] = res
	return res
(n, m) = map(int, input().strip().split())
parents = (n + 1) * [0]
children = [[] for _ in range(n + 1)]
for i in range(2, n + 1):
	j = int(input())
	parents[i] = j
	children[j].append(i)
depths = (n + 1) * [0]
stack = [(1, 1)]
while stack:
	(i, d) = stack.pop()
	depths[i] = d
	for j in children[i]:
		stack.append((j, d + 1))
nrs = (n + 1) * [0]
for _ in range(m):
	(q, si, sj) = input().strip().split()
	if q == 'U':
		(x, k) = (int(si), int(sj))
		fibs = list(fib_pair(k))
		stack = [(x, 0)]
		while stack:
			(y, l) = stack.pop()
			if l >= len(fibs):
				fibs.append((fibs[-1] + fibs[-2]) % mod)
			nrs[y] += fibs[l]
			for z in children[y]:
				stack.append((z, l + 1))
	else:
		(i, j) = (int(si), int(sj))
		if depths[i] < depths[j]:
			(i, j) = (j, i)
		fsum = 0
		while depths[j] < depths[i]:
			fsum += nrs[i]
			i = parents[i]
		while i != j:
			fsum += nrs[i] + nrs[j]
			j = parents[j]
			i = parents[i]
		fsum += nrs[i]
		print(fsum % mod)


mod = 10 ** 9 + 7
cache = {0: (0, 1), 1: (1, 1)}

def fib_pair(n):
	if n in cache:
		return cache[n]
	hn = n // 2
	(f, fp) = fib_pair(hn)
	if n & 1:
		res = ((fp * fp + f * f) % mod, (2 * f + fp) * fp % mod)
	else:
		fm = fp - f
		if fm < 0:
			fm += mod
		res = ((2 * fm + f) * f % mod, (fp * fp + f * f) % mod)
	if n < 1000000:
		cache[n] = res
	return res
(n, m) = map(int, input().strip().split())
parents = (n + 1) * [0]
children = [[] for _ in range(n + 1)]
for i in range(2, n + 1):
	j = int(input())
	parents[i] = j
	children[j].append(i)
depths = (n + 1) * [0]
stack = [(1, 1)]
while stack:
	(i, d) = stack.pop()
	depths[i] = d
	for j in children[i]:
		stack.append((j, d + 1))
nrs = (n + 1) * [0]
for _ in range(m):
	(q, si, sj) = input().strip().split()
	if q == 'U':
		(x, k) = (int(si), int(sj))
		fibs = list(fib_pair(k))
		stack = [(x, 0)]
		while stack:
			(y, l) = stack.pop()
			if l >= len(fibs):
				fibs.append((fibs[-1] + fibs[-2]) % mod)
			nrs[y] += fibs[l]
			for z in children[y]:
				stack.append((z, l + 1))
	else:
		(i, j) = (int(si), int(sj))
		if depths[i] < depths[j]:
			(i, j) = (j, i)
		fsum = 0
		while depths[j] < depths[i]:
			fsum += nrs[i]
			i = parents[i]
		while i != j:
			fsum += nrs[i] + nrs[j]
			j = parents[j]
			i = parents[i]
		fsum += nrs[i]
		print(fsum % mod)


mod = 10 ** 9 + 7
cache = {0: (0, 1), 1: (1, 1)}

def fib_pair(n):
	if n in cache:
		return cache[n]
	hn = n // 2
	(f, fp) = fib_pair(hn)
	if n & 1:
		res = ((fp * fp + f * f) % mod, (2 * f + fp) * fp % mod)
	else:
		fm = fp - f
		if fm < 0:
			fm += mod
		res = ((2 * fm + f) * f % mod, (fp * fp + f * f) % mod)
	if n < 1000000:
		cache[n] = res
	return res
(n, m) = map(int, input().strip().split())
parents = (n + 1) * [0]
children = [[] for _ in range(n + 1)]
for i in range(2, n + 1):
	j = int(input())
	parents[i] = j
	children[j].append(i)
depths = (n + 1) * [0]
stack = [(1, 1)]
while stack:
	(i, d) = stack.pop()
	depths[i] = d
	for j in children[i]:
		stack.append((j, d + 1))
nrs = (n + 1) * [0]
for _ in range(m):
	(q, si, sj) = input().strip().split()
	if q == 'U':
		(x, k) = (int(si), int(sj))
		fibs = list(fib_pair(k))
		stack = [(x, 0)]
		while stack:
			(y, l) = stack.pop()
			if l >= len(fibs):
				fibs.append((fibs[-1] + fibs[-2]) % mod)
			nrs[y] += fibs[l]
			for z in children[y]:
				stack.append((z, l + 1))
	else:
		(i, j) = (int(si), int(sj))
		if depths[i] < depths[j]:
			(i, j) = (j, i)
		fsum = 0
		while depths[j] < depths[i]:
			fsum += nrs[i]
			i = parents[i]
		while i != j:
			fsum += nrs[i] + nrs[j]
			j = parents[j]
			i = parents[i]
		fsum += nrs[i]
		print(fsum % mod)


mod = 10 ** 9 + 7
cache = {0: (0, 1), 1: (1, 1)}

def fib_pair(n):
	if n in cache:
		return cache[n]
	hn = n // 2
	(f, fp) = fib_pair(hn)
	if n & 1:
		res = ((fp * fp + f * f) % mod, (2 * f + fp) * fp % mod)
	else:
		fm = fp - f
		if fm < 0:
			fm += mod
		res = ((2 * fm + f) * f % mod, (fp * fp + f * f) % mod)
	if n < 1000000:
		cache[n] = res
	return res
(n, m) = map(int, input().strip().split())
parents = (n + 1) * [0]
children = [[] for _ in range(n + 1)]
for i in range(2, n + 1):
	j = int(input())
	parents[i] = j
	children[j].append(i)
depths = (n + 1) * [0]
stack = [(1, 1)]
while stack:
	(i, d) = stack.pop()
	depths[i] = d
	for j in children[i]:
		stack.append((j, d + 1))
nrs = (n + 1) * [0]
for _ in range(m):
	(q, si, sj) = input().strip().split()
	if q == 'U':
		(x, k) = (int(si), int(sj))
		fibs = list(fib_pair(k))
		stack = [(x, 0)]
		while stack:
			(y, l) = stack.pop()
			if l >= len(fibs):
				fibs.append((fibs[-1] + fibs[-2]) % mod)
			nrs[y] += fibs[l]
			for z in children[y]:
				stack.append((z, l + 1))
	else:
		(i, j) = (int(si), int(sj))
		if depths[i] < depths[j]:
			(i, j) = (j, i)
		fsum = 0
		while depths[j] < depths[i]:
			fsum += nrs[i]
			i = parents[i]
		while i != j:
			fsum += nrs[i] + nrs[j]
			j = parents[j]
			i = parents[i]
		fsum += nrs[i]
		print(fsum % mod)


mod = 10 ** 9 + 7
cache = {0: (0, 1), 1: (1, 1)}

def fib_pair(n):
	if n in cache:
		return cache[n]
	hn = n // 2
	(f, fp) = fib_pair(hn)
	if n & 1:
		res = ((fp * fp + f * f) % mod, (2 * f + fp) * fp % mod)
	else:
		fm = fp - f
		if fm < 0:
			fm += mod
		res = ((2 * fm + f) * f % mod, (fp * fp + f * f) % mod)
	if n < 1000000:
		cache[n] = res
	return res
(n, m) = map(int, input().strip().split())
parents = (n + 1) * [0]
children = [[] for _ in range(n + 1)]
for i in range(2, n + 1):
	j = int(input())
	parents[i] = j
	children[j].append(i)
depths = (n + 1) * [0]
stack = [(1, 1)]
while stack:
	(i, d) = stack.pop()
	depths[i] = d
	for j in children[i]:
		stack.append((j, d + 1))
nrs = (n + 1) * [0]
for _ in range(m):
	(q, si, sj) = input().strip().split()
	if q == 'U':
		(x, k) = (int(si), int(sj))
		fibs = list(fib_pair(k))
		stack = [(x, 0)]
		while stack:
			(y, l) = stack.pop()
			if l >= len(fibs):
				fibs.append((fibs[-1] + fibs[-2]) % mod)
			nrs[y] += fibs[l]
			for z in children[y]:
				stack.append((z, l + 1))
	else:
		(i, j) = (int(si), int(sj))
		if depths[i] < depths[j]:
			(i, j) = (j, i)
		fsum = 0
		while depths[j] < depths[i]:
			fsum += nrs[i]
			i = parents[i]
		while i != j:
			fsum += nrs[i] + nrs[j]
			j = parents[j]
			i = parents[i]
		fsum += nrs[i]
		print(fsum % mod)


mod = 10 ** 9 + 7
cache = {0: (0, 1), 1: (1, 1)}

def fib_pair(n):
	if n in cache:
		return cache[n]
	hn = n // 2
	(f, fp) = fib_pair(hn)
	if n & 1:
		res = ((fp * fp + f * f) % mod, (2 * f + fp) * fp % mod)
	else:
		fm = fp - f
		if fm < 0:
			fm += mod
		res = ((2 * fm + f) * f % mod, (fp * fp + f * f) % mod)
	if n < 1000000:
		cache[n] = res
	return res
(n, m) = map(int, input().strip().split())
parents = (n + 1) * [0]
children = [[] for _ in range(n + 1)]
for i in range(2, n + 1):
	j = int(input())
	parents[i] = j
	children[j].append(i)
depths = (n + 1) * [0]
stack = [(1, 1)]
while stack:
	(i, d) = stack.pop()
	depths[i] = d
	for j in children[i]:
		stack.append((j, d + 1))
nrs = (n + 1) * [0]
for _ in range(m):
	(q, si, sj) = input().strip().split()
	if q == 'U':
		(x, k) = (int(si), int(sj))
		fibs = list(fib_pair(k))
		stack = [(x, 0)]
		while stack:
			(y, l) = stack.pop()
			if l >= len(fibs):
				fibs.append((fibs[-1] + fibs[-2]) % mod)
			nrs[y] += fibs[l]
			for z in children[y]:
				stack.append((z, l + 1))
	else:
		(i, j) = (int(si), int(sj))
		if depths[i] < depths[j]:
			(i, j) = (j, i)
		fsum = 0
		while depths[j] < depths[i]:
			fsum += nrs[i]
			i = parents[i]
		while i != j:
			fsum += nrs[i] + nrs[j]
			j = parents[j]
			i = parents[i]
		fsum += nrs[i]
		print(fsum % mod)


mod = 10 ** 9 + 7
cache = {0: (0, 1), 1: (1, 1)}

def fib_pair(n):
	if n in cache:
		return cache[n]
	hn = n // 2
	(f, fp) = fib_pair(hn)
	if n & 1:
		res = ((fp * fp + f * f) % mod, (2 * f + fp) * fp % mod)
	else:
		fm = fp - f
		if fm < 0:
			fm += mod
		res = ((2 * fm + f) * f % mod, (fp * fp + f * f) % mod)
	if n < 1000000:
		cache[n] = res
	return res
(n, m) = map(int, input().strip().split())
parents = (n + 1) * [0]
children = [[] for _ in range(n + 1)]
for i in range(2, n + 1):
	j = int(input())
	parents[i] = j
	children[j].append(i)
depths = (n + 1) * [0]
stack = [(1, 1)]
while stack:
	(i, d) = stack.pop()
	depths[i] = d
	for j in children[i]:
		stack.append((j, d + 1))
nrs = (n + 1) * [0]
for _ in range(m):
	(q, si, sj) = input().strip().split()
	if q == 'U':
		(x, k) = (int(si), int(sj))
		fibs = list(fib_pair(k))
		stack = [(x, 0)]
		while stack:
			(y, l) = stack.pop()
			if l >= len(fibs):
				fibs.append((fibs[-1] + fibs[-2]) % mod)
			nrs[y] += fibs[l]
			for z in children[y]:
				stack.append((z, l + 1))
	else:
		(i, j) = (int(si), int(sj))
		if depths[i] < depths[j]:
			(i, j) = (j, i)
		fsum = 0
		while depths[j] < depths[i]:
			fsum += nrs[i]
			i = parents[i]
		while i != j:
			fsum += nrs[i] + nrs[j]
			j = parents[j]
			i = parents[i]
		fsum += nrs[i]
		print(fsum % mod)


mod = 10 ** 9 + 7
cache = {0: (0, 1), 1: (1, 1)}

def fib_pair(n):
	if n in cache:
		return cache[n]
	hn = n // 2
	(f, fp) = fib_pair(hn)
	if n & 1:
		res = ((fp * fp + f * f) % mod, (2 * f + fp) * fp % mod)
	else:
		fm = fp - f
		if fm < 0:
			fm += mod
		res = ((2 * fm + f) * f % mod, (fp * fp + f * f) % mod)
	if n < 1000000:
		cache[n] = res
	return res
(n, m) = map(int, input().strip().split())
parents = (n + 1) * [0]
children = [[] for _ in range(n + 1)]
for i in range(2, n + 1):
	j = int(input())
	parents[i] = j
	children[j].append(i)
depths = (n + 1) * [0]
stack = [(1, 1)]
while stack:
	(i, d) = stack.pop()
	depths[i] = d
	for j in children[i]:
		stack.append((j, d + 1))
nrs = (n + 1) * [0]
for _ in range(m):
	(q, si, sj) = input().strip().split()
	if q == 'U':
		(x, k) = (int(si), int(sj))
		fibs = list(fib_pair(k))
		stack = [(x, 0)]
		while stack:
			(y, l) = stack.pop()
			if l >= len(fibs):
				fibs.append((fibs[-1] + fibs[-2]) % mod)
			nrs[y] += fibs[l]
			for z in children[y]:
				stack.append((z, l + 1))
	else:
		(i, j) = (int(si), int(sj))
		if depths[i] < depths[j]:
			(i, j) = (j, i)
		fsum = 0
		while depths[j] < depths[i]:
			fsum += nrs[i]
			i = parents[i]
		while i != j:
			fsum += nrs[i] + nrs[j]
			j = parents[j]
			i = parents[i]
		fsum += nrs[i]
		print(fsum % mod)


mod = 10 ** 9 + 7
cache = {0: (0, 1), 1: (1, 1)}

def fib_pair(n):
	if n in cache:
		return cache[n]
	hn = n // 2
	(f, fp) = fib_pair(hn)
	if n & 1:
		res = ((fp * fp + f * f) % mod, (2 * f + fp) * fp % mod)
	else:
		fm = fp - f
		if fm < 0:
			fm += mod
		res = ((2 * fm + f) * f % mod, (fp * fp + f * f) % mod)
	if n < 1000000:
		cache[n] = res
	return res
(n, m) = map(int, input().strip().split())
parents = (n + 1) * [0]
children = [[] for _ in range(n + 1)]
for i in range(2, n + 1):
	j = int(input())
	parents[i] = j
	children[j].append(i)
depths = (n + 1) * [0]
stack = [(1, 1)]
while stack:
	(i, d) = stack.pop()
	depths[i] = d
	for j in children[i]:
		stack.append((j, d + 1))
nrs = (n + 1) * [0]
for _ in range(m):
	(q, si, sj) = input().strip().split()
	if q == 'U':
		(x, k) = (int(si), int(sj))
		fibs = list(fib_pair(k))
		stack = [(x, 0)]
		while stack:
			(y, l) = stack.pop()
			if l >= len(fibs):
				fibs.append((fibs[-1] + fibs[-2]) % mod)
			nrs[y] += fibs[l]
			for z in children[y]:
				stack.append((z, l + 1))
	else:
		(i, j) = (int(si), int(sj))
		if depths[i] < depths[j]:
			(i, j) = (j, i)
		fsum = 0
		while depths[j] < depths[i]:
			fsum += nrs[i]
			i = parents[i]
		while i != j:
			fsum += nrs[i] + nrs[j]
			j = parents[j]
			i = parents[i]
		fsum += nrs[i]
		print(fsum % mod)