Vì dịch bệnh COVID19 đang diễn biến theo hướng xấu, CaiWinDao và người yêu là anh XYZ quyết định ở nhà tổ chức trò chơi tính nhẩm nhanh với dãy số để luyện tập cho cuộc thi Siêu trí tuệ mùa 2 :v. Anh XYZ có một mảng \(A\) cho trước gồm \(N\) phần tử được đánh số từ \(1\) tới \(N\). Ban đầu, tất cả các số trong mảng đều bằng \(0\). Anh XYZ đưa ra \(M\) truy vấn trên mảng để CaiWinDao thực hiện các phép tính nhanh, các truy vấn chỉ thuộc một trong \(3\) dạng sau đây:

• 0 x y : CaiWinDao phải đưa ra kết quả của phép tính tổng tất cả các số trong mảng \(A\) từ vị trí \(x\) đến vị trí \(y\) theo modulo \(10^9 + 7\).
• 1 x y : CaiWinDao phải lần lượt cộng thêm \(1.2.3\) vào phần thử thứ \(x\), cộng thêm \(2.3.4\) vào phần tử thứ \(x+1\), ... , cộng thêm \((i+1).(i+2).(i+3)\) vào phần tử thứ \(x+i\), ... và tiếp tục cho đến \(y\).
• 2 x y : CaiWinDao phải lần lượt trừ đi \(1.2.3\) từ phần thử thứ \(x\), trừ đi \(2.3.4\) từ phần tử thứ \(x+1, ... ,\) trừ đi \((i+1).(i+2).(i+3)\) từ phần tử thứ \(x+i\), ... và tiếp tục cho đến \(y\).

Input

• Dòng đầu : gồm 2 số \(N\) và \(M (1 \le N,M \le 10^5)\)
• Dòng hai đến dòng \(M+1\) : gồm 3 số \(x\text{ }y\text{ }z (0 \le x \le 2, 1 \le y \le z \le N), x\) là loại truy vấn, \(y\) và \(z\) là hai đầu mút của đoạn con cần thực hiện truy vấn.

Output

• Với mỗi truy vấn loại \(0\), in ra câu trả lời theo yêu cầu trên từng dòng riêng biệt theo thứ tự xuất hiện của truy vấn đó trong input

Example

8 4
1 1 8
0 2 8
2 4 6
0 5 6

1974
462