Chef's love for Fibonacci numbers helps him to design following interesting problem.
He defines a function F for an array S as follows:

where
- Si denotes a non-empty subset of multiset S.
- sum(Si) denotes the sum of all element of multiset Si.
- Fibonacci(x) denotes the xth Fibonacci number.
Given an array A consisting of N elements. Chef asked you to process following two types of queries on this array accurately and efficiently.
- C X Y: Change the value of Xth element of array to Y i.e AX = Y.
- Q L R: Compute function F over the subarray defined by the elements of array A in the range L to R, both inclusive.

Please see the Note section if you need details regarding Fibonacci function.

-----Input-----
First line of input contains 2 space separated integer N and M denoting the size of array A and the number of queries to be performed. Next line of input contains N space separated integers denoting the elements of array A. Each of next M lines of input contains a query having one of the mentioned two types.

-----Output-----
For each query of type Q, output the value of function F for the given range of array A.

-----Constraints-----
- 1 ≤ N, M ≤ 105
- 1 ≤ Ai, Y ≤ 109
- 1 ≤ L, R, X ≤ N
-  type = {'C', 'Q'} 

-----Subtasks-----
- Subtask 1 (20 points) : 1 ≤ N, M ≤ 1000, 1 ≤ Ai, Y ≤ 106, type = { 'Q' } 
- Subtask 2 (20 points) : 1 ≤ N, M ≤ 50000, 1 ≤ Ai, Y ≤ 109, type = { 'C', Q' } 
- Subtask 3 (30 points) : 1 ≤ N, M ≤ 105, 1 ≤ Ai, Y ≤ 109, type = { 'Q' } 
- Subtask 4 (30 points) : 1 ≤ N, M ≤ 105, 1 ≤ Ai, Y ≤ 109, type = { 'C', Q' }

-----Example-----
Input
3 5
1 2 3
Q 1 2
Q 2 3
C 1 2
Q 1 2
Q 1 3

Output
4
8
5
30

-----Explanation:-----
- Q1 : F = Fibonacci(1) + Fibonacci(2) + Fibonacci(1+2) = 4 % 1000000007 = 4
- Q2 : F = Fibonacci(2) + Fibonacci(3) + Fibonacci(2+3) = 8 % 1000000007 = 8
- Q3 : A = {2, 2, 3}
- Q4 : F = Fibonacci(2) + Fibonacci(2) + Fibonacci(2+2) = 5 % 1000000007 = 5
- Q5 : F = Fibonacci(2) + Fibonacci(2) + Fibonacci(3) + Fibonacci(2+2) + Fibonacci(2+3) + Fibonacci(2+3) + Fibonacci(2+2+3) = 30 % 1000000007 = 30

-----Note-----
FibonacciK denotes the Kth Fibonacci number. Fibonacci series is defined as follows:
- For 1 ≤ K ≤ 2, FibonacciK = 1
- Otherwise, FibonacciK = FibonacciK-1 + FibonacciK-2
Please check this link for more details about Fibonacci numbers.

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
m = 1000000007

def mul(a, b):
	return [(a[0] * b[0] + a[1] * b[2]) % m, (a[0] * b[1] + a[1] * b[3]) % m, (a[2] * b[0] + a[3] * b[2]) % m, (a[2] * b[1] + a[3] * b[3]) % m]

def f(n):
	if n == 0:
		return 0
	(v1, v2, v3) = (1, 1, 0)
	for rec in bin(n)[3:]:
		v2 = v2 % m
		v1 = v1 % m
		v3 = v3 % m
		calc = v2 * v2
		(v1, v2, v3) = (v1 * v1 + calc, (v1 + v3) * v2, calc + v3 * v3)
		if rec == '1':
			(v1, v2, v3) = (v1 + v2, v1, v2)
	return [v1 + 1, v2, v2, v3 + 1]

def q(X, Y):
	nonlocal A
	s = [1, 0, 0, 1]
	for v in A[X - 1:Y]:
		s = mul(s, f(v))
	return s[1] % m
(N, M) = list(map(int, input().split()))
A = list(map(int, input().split()))
for _ in range(M):
	[T, X, Y] = input().split()
	(X, Y) = (int(X), int(Y))
	if T == 'Q':
		print(q(X, Y))
	else:
		A[X - 1] = Y