Khi xuất hiện dịch bệnh ~X~, các nhà khoa học đã nghiên cứu sự thay đổi gene của các chứng virus. Chuỗi gene của virus là dãy ~N~ phức hợp proteins được mã hóa thành các số nguyên ~a_1, a_2, \ldots, a_N~ (~1 \le i \le N~).

Ban đầu, chuỗi gene được chứa toàn bộ các proteins ~0~. Chúng có rất nhiều lần biến đổi khác nhau. Mỗi lần biến đổi, chúng thay đổi các proteins trong đoạn ~[L, R]~ theo phép toán ~T_K~. Nghĩa là các proteins trong đoạn ~[L, R]~ tăng lên một lượng giá trị là số fibonacci thứ ~K~ chia đồng dư cho ~10^3 + 7~ (phép modulo). Với dãy số fibonacci được định nghĩa như sau: $$F_K = F_{K - 1} + F_{K - 2} \text{ với } F_1 = 1, F_2 = 1.$$

Để làm cơ sở nghiên cứu, các nhà khoa học đã ghi lại các câu truy vấn cho biết quá trình biến đổi gene. Bên cạnh đó, họ có các câu truy vấn tính tổng các proteins trong đoạn ~[L, R]~ tại một số thời điểm.

Yêu cầu: Viết chương trình thực hiện lần lượt ~Q~ truy vấn, mỗi truy vấn có thể là một trong hai dạng sau:

• ~1~ ~L~ ~R~ ~K~: Biến đổi các proteins trong đoạn ~[L, R]~ theo phép toán ~T_K~.

• ~2~ ~L~ ~R~: Tính tổng các proteins trong đoạn ~[L, R]~.

(~1 \le L \le R \le N~; ~1 \le K \le 10^{18}~).

Input

• Dòng đầu tiên chứa hai số nguyên ~N~, ~Q~ (~1 \le N, Q \le 2 \cdot 10^5~).

• Trên ~Q~ dòng tiếp theo, mỗi dòng chứa một truy vấn theo mô tả như trên.

Các số trên một dòng cách nhau bởi ít nhất một dấu khoảng trắng.

Ràng buộc: Tổng các giá trị ~a_i~ trong quá trình truy vấn sẽ không vượt quá ~10^9~.

Output

Ghi ra kết quả của các truy vấn dạng ~2~, mỗi kết quả ghi trên một dòng.

Sample Input 1

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

Sample Output 1

6
25

Sample Input 2

3 4
1 1 1 5
1 2 2 7
1 1 3 8
2 1 3

Sample Output 2

81

Notes

Giải thích:

1. • Ban đầu, các phức hợp proteins là ~\{0, 0, 0, 0, 0\}~.

   • Truy vấn đầu tiên, biến đổi đoạn ~[2, 4]~ theo ~T_3~ nghĩa là tăng lên ~2~ đơn vị nên ta có chuỗi gen ~\{0, 2, 2, 2, 0\}~.

   • Truy vấn thứ hai, tổng đoạn ~[1, 5]~ ta được giá trị là ~6~.

   • Truy vấn thứ ba và thứ tư, lần lượt là ~\{5, 7, 7, 2, 0\}~ và ~\{5, 7, 7, 10, 8\}~.

   • Truy vấn cuối cùng, tổng đoạn ~[3, 5]~ ta được ~(7 + 10 + 8) = 25~.

2. Chuỗi gene có các phức hợp proteins thay đổi lần lượt như sau: ~\{0, 0, 0\}~, ~\{5, 0, 0\}~, ~\{5, 13, 0\}~, ~\{26, 34, 21\}~. Kết quả cuối cùng sẽ là ~(26 + 34 + 21) = 81~.