Problem M
Fibonacci Gjöf

Siggi got an array of $n$ positive integers, $x_1, x_2, \ldots , x_ n$ as a birthday gift from his grandmother. These integers aren’t just any integers, they denote Fibonacci numbers. The first Fibonacci number is $1$, the second Fibonacci number is also $1$ and the ones after that are the sum of the previous two Fibonacci numbers. The third Fibonacci number is thus $2$ since $1+1=2$, the fourth Fibonacci number is $3$ since $1+2=3$, the fifth Fibonacci number is $5$ since $2+3=5$ and so on. We denote the $n$-th Fibonacci number by $\mathrm{Fib}(n)$.

Siggi is playing around with his new array and he greatly enjoys applying the two following operations to the array:

1. Siggi chooses a positive integer $d$ and some interval in the array that starts at $l$ and ends at $r$, i.e. $x_ l, x_{l+1}, \ldots , x_ r$. He then adds the value $d$ to all values in the array in this interval.

2. Siggi chooses some interval in the array starting at $l$ and ending at $r$ and calculates the sum of all the Fibonacci numbers that these integers denote:

   \[ \mathrm{Fib}(x_ l) + \mathrm{Fib}(x_ l+1) + \cdots + \mathrm{Fib}(x_ r) \]

He’s getting a bit tired of doing this by hand and asks you for help. Given the original array that Siggi got as a present and what operations Siggi applies, can you calculate the answer for every operation of the second type that Siggi applies?

Input

The first line of the input contains two integers $n$ and $m$ ($1 \leq n, m \leq 10^5$), the size of Siggi’s array and the number of operations he applies.

The next line contains $n$ integers $x_1,x_2,\ldots ,x_ n$ separated by spaces, denoting the values in the original array Siggi got as a birthday present ($1 \leq x_ i\leq 10^9$ for all $i$). Then there are $m$ lines, one for each operation Siggi applies, but each of them is of one of the following two types:

• 1 $l$ $r$ $d$: Siggi applies the first operation using the value $d$ on the interval $l$, $r$ ($1 \leq l \leq r \leq n$, $1 \leq d \leq 10^9$).

• 2 $l$ $r$: Siggi applies the second operation on the interval $l$, $r$ ($1 \leq l \leq r \leq n$).

Output

For each operation of the second type, print a line with the value of the sum that Siggi calculates. Since this value can become very large we ask you to print the remainder of that value after dividing it by $10^9+7$.

Scoring

4 5
1 1 1 1
2 2 3
1 1 2 2
2 2 3
1 2 2 4
2 1 4

2
3
17

5 6
10 7 3 5 4
2 1 1
2 2 3
2 4 5
1 1 3 20
1 3 5 100
2 1 5

55
15
8
403785010