피보나치 선물

꼬마 Siggi는 할머니에게 생일 선물로 $n$개의 양의 정수로 이루어진 배열 $x_1, x_2, \ldots, x_n$을 받았다. 이 정수들은 단순한 정수가 아니라 피보나치 수의 번호를 나타낸다. $1$번 피보나치 수는 $1$이고, $2$번 피보나치 수도 $1$이며, 그다음 피보나치 수는 항상 직전의 두 피보나치 수를 더하여 계산한다. 따라서 $3$번 피보나치 수는 $1+1=2$이고, $4$번 피보나치 수는 $1+2 = 3$이며, $5$번 피보나치 수는 $2+3=5$이고, 이와 같은 방식으로 계속된다. $n$번 피보나치 수를 $\mathrm{Fib}(n)$로 나타낸다.

꼬마 Siggi는 새 배열을 가지고 놀고 있으며, 배열에 다음 두 연산을 수행하는 것을 좋아한다.

• Siggi는 양의 정수 $d$와 $l$에서 시작하여 $r$에서 끝나는 배열의 어떤 구간, 즉 $x_l, x_{l+1}, \ldots, x_{r}$를 선택한다. 그런 다음 이 구간에 있는 배열의 모든 원소에 정수 $d$를 더한다.

• Siggi는 $l$에서 시작하여 $r$에서 끝나는 배열의 어떤 구간을 선택하고, 이 구간의 정수들이 나타내는 모든 피보나치 수의 합을 계산한다: $\mathrm{Fib}(x_l) + \mathrm{Fib}(x_l+1) + \cdots + \mathrm{Fib}(x_r)$

이제 그는 이 작업을 손으로 하는 데 조금 싫증이 나서 당신에게 도움을 요청한다. 꼬마 Siggi가 생일 선물로 받은 초기 배열과 꼬마 Siggi가 수행하는 연산들이 주어질 때, 꼬마 Siggi가 수행하는 각 $2$번 연산의 답을 계산할 수 있는가?

점수

그룹 | 점수 | 제한

1 | 22 | $n \leq 100$, $m \leq 32$, $d = 1$, $x_i = 1$

2 | 26 | $n \leq 1\,000$, $m \leq 100$, $d = 1$, $x_i = 1$

3 | 25 | $n \leq 1\,000$, $m \leq 100$

4 | 27 | 추가 제한 없음

입력의 첫째 줄에는 두 정수 $n$과 $m$가 주어진다. 이들은 꼬마 Siggi의 배열 크기와 그가 수행하는 연산의 개수이다 ($1 \leq n, m \leq 10^5$).

다음 줄에는 꼬마 Siggi가 생일 선물로 받은 배열을 나타내는, 공백으로 구분된 $n$개의 정수 $x_1,x_2,\ldots, x_n$가 주어진다 (모든 $i$에 대해 $1 \leq x_i\leq 10^9$).

이어서 Siggi가 수행하는 각 연산마다 한 줄씩, 총 $m$개의 줄이 주어지며, 각 줄은 다음 두 형식 중 하나이다.

• 1 $l$ $r$ $d$: 꼬마 Siggi는 $l$에서 $r$까지의 구간에 수 $d$를 사용하여 $1$번 연산을 수행한다. ($1 \leq l \leq r \leq n$, $1 \leq d \leq 10^9$)

• 2 $l$ $r$: 꼬마 Siggi는 $l$에서 $r$까지의 구간에 $2$번 연산을 수행한다. ($1 \leq l \leq r \leq n$)

각 $2$번 연산에 대해 Siggi가 계산한 합의 값을 한 줄에 출력한다. 이 수는 다소 커질 수 있으므로, 답을 $10^9+7$로 나눈 나머지를 출력한다.