Bé Cún có một dãy số gồm \(N\) phần tử \(A_1,\ A_2,\ ...,\ A_N\). Bé Cún sẽ thực hiện \(M\) truy vấn, mỗi truy vấn sẽ thuộc một trong hai loại sau:

• \(1\ l\ r\ x:\) Tăng tất cả phần tử trong đoạn \([l,r]\) lên \(x\).

• \(2\ l\ r:\) In ra tổng tất cả các giá trị \(f(A_i)\ (l \le i \le r)\) với \(f(x)\) là số Fibonanci thứ \(x\), vì kết quả có thể rất lớn nên chỉ in ra kết quả sau khi chia lấy dư \((10^9+7).\)

Chúng ta định nghĩa số Fibonanci là số Fibonanci: \(f(1) = 1, f(2) = 1, f(x) = f(x-1) + f(x-2)\) với \(x \ge 3\)

Dữ liệu

• Dòng đầu tiên ghi hai số nguyên \(N\) và \(M\ (1 \le N \le 10^5; 1 \le M \le 10^5).\)

• Dòng thứ hai ghi \(N\) số số nguyên \(A_1, A_2, ..., A_N\ (1 \le A_i \le 10^9).\)

• \(M\) dòng tiếp theo ghi \(M\) truy vấn, truy vấn thứ \(i\) thuộc một trong hai truy vấn trên \((1 \le l_i \le r_i \le N; 1 \le x_i \le 10^9)\)

• Dữ liệu đảm bảo luôn có một truy vấn loại \(2.\)

Kết quả

Với mỗi truy vấn loại \(2\), in ra một số nguyên là kết quả tương ứng.

Ví dụ

Giải thích

• Ban đầu dãy \(A\) bao gồm \(1, 1, 2, 1, 1\)
• Kết quả của truy vấn loại \(2\) đầu tiên là \(f(1) + f(1) + f(2) + f(1) + f(1) = 1 + 1 + 1 + 1 + 1 = 5\)
• Sau truy vấn \(1\ 2\ 4\ 2\), dãy \(A\) trở thành \(1,\ 3,\ 4,\ 3,\ 1\)
• Kết quả của truy vấn loại \(2\) thứ hai là \(f(3) + f(4) + f(3) = 2 + 3 + 2 = 7\)
• Kết quả của truy vấn loại \(2\) thứ ba là \(f(1) + f(3) + f(4) + f(3) + f(1) = 1 + 2 + 3 + 2 + 1 = 9\)