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 a_{1}, a_{2}, ..., a_{n}. Your task is to perform over the sequence m consecutive operations of the following type:
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 a_{1}, a_{2}, ..., a_{n}. Your task is to perform over the sequence m consecutive operations of the following type:
- For given numbers l_{i} and r_{i} you've got to calculate ∑ f(a_{k}) : k=l_{i}..r_{i}, where f(0)=f(1)=1 and f(i)=f(i-1)+f(i-2): i ≥ 2.
- For a group of three numbers l_{i}, r_{i}, d_{i} you should increase value a_{x} by d_{i} for all x (l_{i} ≤ x ≤ r_{i})
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 ≤ 10^{5}) - the number of integers in the sequence. The second line contains n integers a_{1}, a_{2}, ..., a_{n} (1 ≤ a_{i} ≤ 10^{7}), separated by spaces. The third line contains one integer m (1 ≤ m ≤ 10^{5}) - the number of operations. Then follow m lines that describe the operations. Each line starts with an integer t_{i} (1 ≤ t_{i} ≤ 2) indicating the operation type:
- If t_{i} = 1, then next follow two integers l_{i} and r_{i} (1 ≤ l_{i} ≤ r_{i} ≤ n), separated by spaces.
- If t_{i} = 2, then next follow three integers l_{i}, r_{i} and d_{i} (1 ≤ l_{i} ≤ r_{i} ≤ n, 0 ≤ d_{i} ≤ 100), separated by spaces.
Output:
For each query where t_{i} = 1, print the calculated sum modulo 1000000007 (10^{9} + 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