Homework With Fibonacci -

can give me idea how solve problem? given sequence of integers a1, a2, ..., an. task perform on sequence m consecutive operations of following type: given numbers li , ri you've got calculate ∑ f(ak) : k=li..ri, f(0)=f(1)=1 , f(i)=f(i-1)+f(i-2): ≥ 2. group of 3 numbers li, ri, di should increase value ax di x (li ≤ x ≤ ri) input:

the first line contains number of test cases (at 15).

for each test case:

• the first line contains 1 integer n (1 ≤ n ≤ 105) - number of integers in sequence.
• the second line contains n integers a1, a2, ..., (1 ≤ ai ≤ 107), separated spaces.
• the third line contains 1 integer m (1 ≤ m ≤ 105) - number of operations.
• then follow m lines describe operations. each line starts integer ti (1 ≤ ti ≤ 2) indicating operation type:
  • if ti = 1, next follow 2 integers li , ri (1 ≤ li ≤ ri ≤ n), separated spaces.
  • if ti = 2, next follow 3 integers li, ri , di (1 ≤ li ≤ ri ≤ n, 0 ≤ di ≤ 100), separated spaces.

output:

for each query ti = 1, print calculated sum modulo 1000000007 (109 + 7).

i tried use fenwick tree change values in given array have problem because need o(n*m) in worst case calculate sum of fibonacci queries. there better aproach?