Sasha và mảng (Sasha and Array)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Mảng chỉ số Fibonacci $a_i$. Update 1 l r x tăng mọi $a_i$ trong đoạn thêm $x$. Query 2 l r hỏi $\sum f(a_i)$ modulo $10^9+7$.

Input

Dòng đầu chứa $n,m$. Dòng thứ hai chứa $a_1,a_2,\ldots,a_n$. Mỗi trong $m$ dòng sau là:

• 1 l r x: tăng mọi $a_i$ trong $[l,r]$ thêm $x$.
• 2 l r: hỏi $\sum_{i=l}^{r} f(a_i)$ modulo $10^9+7$.

Output

Mỗi truy vấn loại 2 in đáp án modulo $10^9+7$.

Subtask

• Subtask 1 (20%): $n$ và số thao tác không vượt 30; các điều kiện còn lại giữ như đề đầy đủ.

• Subtask 2 (30%): $n$ và số thao tác không vượt 3000; các điều kiện còn lại giữ như đề đầy đủ.

• Subtask 3 (50%): toàn bộ giới hạn:

• $1\le n,m\le10^5$

• $1\le a_i,x\le10^9$

Ví dụ

Input

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

Output

5
7
9

Giải thích

Ban đầu tổng Fibonacci là 5. Sau khi tăng các chỉ số ở [2,4] thêm 2, mảng chỉ số thành [1,3,4,3,1]; các truy vấn tiếp theo cho 7 và 9.