## 24 hour archive: Problem

###
** 2819
- Homework with Fibonacci** ** 2819 - Homework with Fibonacci** ** 2819 - Homework with Fibonacci**

#### Description

**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: , 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)**.

**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: , 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)**.

**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: , 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 specification

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**a1, a2, ..., an****(1 ≤ ai ≤ 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**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.

**(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

**a1, a2, ..., an**

**(1 ≤ ai ≤ 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

**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.

**(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

**a1, a2, ..., an**

**(1 ≤ ai ≤ 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

**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 specification

For each query where ti = 1, print the calculated sum modulo

**1000000007 (10^9 + 7)**.
For each query where ti = 1, print the calculated sum modulo

**1000000007 (10^9 + 7)**.**(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

**a1, a2, ..., an**

**(1 ≤ ai ≤ 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

**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.

#### Sample input

`1`

5

3 1 2 5 6

3

1 1 3

2 2 4 2

1 2 5

#### Sample output

`6`

42

#### Hint(s)

,

,

,