Sasha và Mảng

Cho một mảng số nguyên $a_1,a_2,\dots ,a_n$. Bạn cần thực hiện $m$ truy vấn thuộc hai loại:

• Loại 1: 1 l r x — tăng tất cả các phần tử trên đoạn từ $l$ đến $r$ lên $x$ đơn vị.
• Loại 2: 2 l r — tính tổng ${\sum }_{i=l}^{r}f(a_i)$, trong đó $f(k)$ là số Fibonacci thứ $k$. Vì kết quả có thể rất lớn, hãy in ra phần dư của nó khi chia cho ${10}^9+7$.

Dãy Fibonacci được định nghĩa như sau: $f(1)=1$, $f(2)=1$, và $f(k)=f(k-1)+f(k-2)$ với mọi $k>2$.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$ — số phần tử của mảng và số truy vấn.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.
• $m$ dòng tiếp theo, mỗi dòng mô tả một truy vấn theo định dạng nêu trên.

Dữ liệu bảo đảm có ít nhất một truy vấn loại 2.

Dữ liệu ra

Với mỗi truy vấn loại 2, in ra một dòng chứa kết quả tương ứng theo modulo ${10}^9+7$.

Ràng buộc

• $1\le n\le {10}^5$
• $1\le m\le {10}^5$
• $1\le a_i\le {10}^9$
• $1\le l\le r\le n$
• $1\le x\le {10}^9$

Ví dụ