[placeholder] đã ngồi nghĩ 3 ngày 3 đêm nhưng không ra được cốt truyện cho bài này.

Cho bảng ~M~ kích thước ~n \times n~ gồm các số nguyên dương. Bạn phải xử lý ~q~ truy vấn gồm 2 loại:

- ~1\; x\; y\; z~: Tìm số lớn nhất trong bảng con ~z \times z~ có góc trên-trái là ô ~(x,y)~. Ô trên-trái của bảng là ô ~(1,1)~.

- ~2\; x\; y~: Dịch (cyclic shift) bảng ~x~ ô theo chiều ngang và ~y~ ô theo chiều dọc. Hình dưới minh họa bảng ~4 \times 4~ với ~x=1~ và ~y=2~

Luwu ý: Do kích thước lớn, để giảm thời gian nhập-xuất, input-output của bài toán được xử lý đặc biệt.

Input

Dòng đầu tiên chứa 2 số ~n, q~ (~n \leq 1,000~, ~q \leq 2,000,000~).

Dòng tiếp theo chứa 2 số ~A_0, B_0~ (~A, B < 10^9+7~).

Dòng cuối cùng chứa 4 số ~C_0, D_0, E_0, F_0~ (~C < 10^9+7, D, E, F < n~).

Với ~i \geq 1~:

Các dãy ~A, B, C~ được định nghĩa như sau:

- ~X_1~ = ~1+((X_0*X_0)\; mod\; 10^9+7)~

- ~X_i~ = ~1+((X_{i-1}+X_{i-2})\; mod\; 10^9+7)\; (i \geq 2)~

Các dãy ~D, E, F~ được định nghĩa như sau:

- ~X_1~ = ~1+((X_0*X_0)\; mod\; n)~

- ~X_i~ = ~1+((X_{i-1}+X_{i-2})\; mod\; n)\; (i \geq 2)~

Dãy ~L~ được định nghĩa như sau: ~L_i = n-max(D_i,E_i)~

Bảng ~M~ được tính bằng công thức:

- ~a_{i,j}: (A_i + B_j)\; mod \; 10^9+7~

Với truy vấn thứ ~i~, nếu ~C_i\; \&\; 1=0~ thì truy vấn đó sẽ có dạng:

- ~1\; D_i\; E_i\; [1+(L_i\; \&\; (L_i \oplus F_i))]~

Ngược lại, nếu ~C_i\; \&\; 1=1~ thì truy vấn đó sẽ có dạng:

- ~2\; D_i\; E_i~

Trong đó: ~\&, \oplus~ là toán tử AND, XOR

Output

Với mỗi ~1,000~ truy vấn loại 1, ta in ra tổng đáp án của các truy vấn đó ~mod\; 10^9+7~ trên các dòng khác nhau.

Ví dụ: Với test có ~3456~ truy vấn loại 1, output có dạng như sau:

~(ans_1\; +\; ...\; +\; ans_{1000})\; mod\; 10^9+7~

~(ans_{1001}\;+\;...\;+\;ans_{2000})\; mod\; 10^9+7~

~(ans_{2001}\;+\;...\;+\;ans_{3000})\; mod\; 10^9+7~

~(ans_{3001}\;+\;...\;+\;ans_{3456})\; mod\; 10^9+7~

Sample Input 1

7 10
2 3
177013 4 5 6

Sample Output 1

262

Notes

Giải thích ví dụ 1:

Bảng số :

Các truy vấn: