Homework with Fibonacci

Statement:

Rodrigo Díaz de Vivar (1043 - July 10, 1099), known as Cid Campeador (“The lord-master of military arts”), was a Castillian nobleman, military leader, ferocious warrior, and diplomat that fought against the Moors. El Cid’s legendary martial abilities have fueled his reputation as an outstanding battlefield commander and one of the greatest heroes in Spain’s history.
El Cid before become a great warrior, he was a lover of mathematics and puzzles in his childhood. But once, he stuck with the following problem:
You are given a sequence of integers a1, a2, ..., an. Your task is to perform over the sequence m consecutive operations of the following type:
  1. For given numbers li and ri you've got to calculate ∑ f(ak) : k=li..ri, where f(0)=f(1)=1 and f(i)=f(i-1)+f(i-2): i ≥ 2.
  2. For a group of three numbers li, ri, di you should increase value ax by di for all x (li ≤ x ≤ ri)

Input:

The first line contains the number of test cases (at most 15). For each test case: The first line contains one integer n (1 ≤ n ≤ 105) - the number of integers in the sequence. The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 107), separated by spaces. The third line contains one integer m (1 ≤ m ≤ 105) - the number of operations. Then follow m lines that describe the operations. Each line starts with an integer ti (1 ≤ ti ≤ 2) indicating the operation type:
  • If ti = 1, then next follow two integers li and ri (1 ≤ li ≤ ri ≤ n), separated by spaces.
  • If ti = 2, then next follow three integers li, ri and di (1 ≤ li ≤ ri ≤ n, 0 ≤ di ≤ 100), separated by spaces.

Output:

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

Example input:
1
5
3 1 2 5 6
3
1 1 3
2 2 4 2
1 2 5
Example output:
6
42
Time and memory limit:

  • 10s
  • 128MB

Problem source: Caribbean Online Judge