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.

Difficulty: interview

Starter code:

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