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.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = "m= 1000000007\ndef mul(a,b):\n return [(a[0]*b[0]+a[1]*b[2])%m,\n   (a[0]*b[1]+a[1]*b[3])%m,\n   (a[2]*b[0]+a[3]*b[2])%m,\n   (a[2]*b[1]+a[3]*b[3])%m] \ndef f(n):\n if n==0:\n  return 0\n v1, v2, v3 = 1, 1, 0 \n for rec in bin(n)[3:]:\n  v2=v2%m\n  v1=v1%m\n  v3=v3%m\n  calc = (v2*v2)\n  v1, v2, v3 = (v1*v1+calc), ((v1+v3)*v2), (calc+v3*v3)\n  if rec=='1': v1, v2, v3 = v1+v2, v1, v2\n return [v1+1,v2,v2,v3+1]\n\ndef q(X,Y):\n nonlocal A\n s = [1,0,0,1]\n for v in A[X-1:Y]:\n  s = mul(s,f(v))\n return s[1]%m\n\nN,M = list(map(int,input().split()))\nA=list(map(int,input().split()))\nfor _ in range(M):\n [T,X,Y] = input().split()\n X,Y = int(X),int(Y)\n if T=='Q':\n  print(q(X,Y))\n else:\n  A[X-1]=Y"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: