Fibonacci Queries

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
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
 S_{i} denotes a nonempty subset of multiset S.
 sum(S_{i}) denotes the sum of all element of multiset S_{i}.
 Fibonacci(x) denotes the x^{th} 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 X^{th} element of array to Y i.e A_{X} = 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 ≤ 10^{5}
 1 ≤ A_{i}, Y ≤ 10^{9}
 1 ≤ L, R, X ≤ N
 type = {'C', 'Q'}
Subtasks
 Subtask 1 (20 points) : 1 ≤ N, M ≤ 1000, 1 ≤ A_{i}, Y ≤ 10^{6}, type = { 'Q' }
 Subtask 2 (20 points) : 1 ≤ N, M ≤ 50000, 1 ≤ A_{i}, Y ≤ 10^{9}, type = { 'C', Q' }
 Subtask 3 (30 points) : 1 ≤ N, M ≤ 10^{5}, 1 ≤ A_{i}, Y ≤ 10^{9}, type = { 'Q' }
 Subtask 4 (30 points) : 1 ≤ N, M ≤ 10^{5}, 1 ≤ A_{i}, Y ≤ 10^{9}, 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:
 Q_{1} : F = Fibonacci(1) + Fibonacci(2) + Fibonacci(1+2) = 4 % 1000000007 = 4
 Q_{2} : F = Fibonacci(2) + Fibonacci(3) + Fibonacci(2+3) = 8 % 1000000007 = 8
 Q_{3} : A = {2, 2, 3}
 Q_{4} : F = Fibonacci(2) + Fibonacci(2) + Fibonacci(2+2) = 5 % 1000000007 = 5
 Q_{5} : F = Fibonacci(2) + Fibonacci(2) + Fibonacci(3) + Fibonacci(2+2) + Fibonacci(2+3) + Fibonacci(2+3) + Fibonacci(2+2+3) = 30 % 1000000007 = 30
Note
Fibonacci_{K} denotes the K^{th} Fibonacci number. Fibonacci series is defined as follows:
 For 1 ≤ K ≤ 2, Fibonacci_{K} = 1
 Otherwise, Fibonacci_{K} = Fibonacci_{K1} + Fibonacci_{K2}
Please check this link for more details about Fibonacci numbers.
Author:  ma5termind 
Tester:  xcwgf666 
Editorial  http://discuss.codechef.com/problems/FIBQ 
Tags  april16 fibonacci ma5termind medium segmenttree 
Date Added:  12012016 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.4, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions