Hạo đang phát triển một hệ thống quản lý dữ liệu cho một tổ chức đang chăm sóc cây xanh trong thành phố. Tổ chức này có \(N\) cây được xếp thành một hàng dài và mỗi cây có một chỉ số sức khỏe ban đầu là \(0\). Trong quá trình bảo dưỡng cây, sẽ có nhiều yêu cầu bảo trì khác nhau, và bạn cần phải xử lý hai loại yêu cầu sau:

• \(1\) \(L\) \(R\) \(K\): Tăng sức khỏe của tất cả các cây từ vị trí thứ \(L\) đến \(R\) lên một lượng tương ứng với giá trị dinh dưỡng từ một loại phân đặc biệt. Giá trị này chính là số Fibonacci thứ \(K\) tính theo \(modulo\) \(1007\)
• \(2\) \(L\) \(R\): Tính tổng chỉ số sức khỏe của các cây từ vị trí \(L\) đến \(R\).

Yêu cầu

• Với mỗi yêu cầu bón phân, Hạo cần phải cập nhật chỉ số sức khỏe của các cây trong đoạn được yêu cầu.
• Với mỗi yêu cầu kiểm tra sức khỏe, Hạo cần trả về tổng chỉ số sức khỏe của các cây trong đoạn tương ứng.
• Hãy giúp Hạo lập trình để xử lý các yêu cầu trên.

Ràng buộc

• \(1 \le L \le R \le N\)
• \(0 \le K \le 10^{18}\)
• \(1 \le N,Q \le 2 \times 10^5\)
• \(A_i \le 10^9\)

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(N,Q\)
• 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.

Dữ liệu ra

• 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.

Input 1

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

Output 1

6
25

Input 2

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

Output 2

81