Hàm số ~\mathrm{F}(x)~ được định nghĩa như sau:

$$\displaystyle \mathrm{F}(x) = \begin{cases} 0 & \text{khi } x = 0 \\ 1 & \text{khi } x = 1 \\ \mathrm{F}(x-1) + \mathrm{F}(x-2) & \text{khi } x > 1 \end{cases} $$

Cho mảng số nguyên ~A~ gồm ~N~ phần tử được đánh số từ ~1~ đến ~N~. Thực hiện ~Q~ truy vấn thuộc một trong hai loại sau:

• Loại ~1~ có dạng 1 L R X ~(~~L~, ~R~, ~X~ là các số nguyên, ~1 \le L \le R \le N~, ~1 \le X \le 10^{12})~: Tăng giá trị mỗi phần tử ~A_i~ ~(L \le i \le R)~ lên ~X~ đơn vị.
• Loại ~2~ có dạng 2 L R ~(~~L~, ~R~ là các số nguyên, ~1 \le L \le R \le N)~: Tính giá trị biểu thức ~ \displaystyle \sum_{i=L}^{R} \mathrm{F}(A_i)~ với kết quả chia lấy dư cho ~10^9+7~.

Input

• Dòng đầu tiên chứa số nguyên ~N~ ~(1 \le N \le 5.10^5)~.
• Dòng tiếp theo chứa ~N~ số nguyên ~A_i~ ~(1 \le A_i \le 10^{12})~.
• Dòng tiếp theo chứa số nguyên ~Q~ ~(1 \le Q \le 5.10^5)~.
• ~Q~ dòng tiếp theo, dòng thứ ~i~ mô tả truy vấn thuộc một trong hai loại trên.
• Dữ liệu đảm bảo có ít nhất một truy vấn loại ~2~.

Output

• Với mỗi truy vấn loại ~2~, in ra kết quả trên một dòng.

Examples

Sample Input

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

Sample Output

6
11
17

Scoring

• Subtask ~1~ với ~20\%~ số điểm: ~N,Q \le 2000~, ~A_i \le 2000~ với mọi ~1 \le i \le N~, ~X \le 2000~ với mọi truy vấn loại ~1~
• Subtask ~2~ với ~20\%~ số điểm: ~N,Q \le 2000~
• Subtask ~3~ với ~20\%~ số điểm: Không có truy vấn loại ~1~
• Subtask ~4~ với ~40\%~ số điểm: Không có ràng buộc gì thêm