Cho một mảng ~N~ số nguyên dương ~A~ và số nguyên ~C~. Xử lý ~Q~ truy vấn thuộc một trong ba dạng sau:

• 1 l r v: Thực hiện phép gán ~A_i := A_i \cdot v~ với mọi ~l \le i \le r~.

• 2 l r v: Thực hiện phép gán ~A_i := A_i + v~ với mọi ~l \le i \le r~.

• 3 l r: Định nghĩa ~f(x,y) = \sum_{i=x}^y A_i~. Với mỗi ~0 \le K \le 4~, tính tổng ~(f(x,y)+C)^K~ với mọi cặp ~(l,r)~ thỏa mãn ~l \le x \le y \le r~ theo modulo ~1000000007~. Nói cách khác, với mỗi ~K~ thỏa mãn ~0 \le K \le 4~, in ra:

  ~\left(\sum_{x=l}^r \sum_{y=x}^r \left(C+\sum_{i=x}^y A_i\right)^K\right) \bmod 1000000007~

Chú ý: Thí sinh không cần trả lời đúng với mọi ~K~ để được điểm. Xem phần Scoring để biết thêm chi tiết.

Input

Dòng đầu tiên là ba số ~N,Q,C~ ~(1 \le N,Q \le 100000, 0 \le C < 1000000007)~.

Dòng thứ hai là ~N~ số nguyên ~A_i~ ~(1 \le A_i < 1000000007)~.

Sau dòng thứ hai là ~Q~ dòng, dòng thứ ~i~ biểu diễn cho truy vấn thứ ~i~ và thuộc một trong ba dạng:

• 1 l r v ~(1 \le l \le r \le n, 1 \le v < 1000000007)~: Truy vấn dạng ~1~

• 2 l r v ~(1 \le l \le r \le n, 1 \le v < 1000000007)~: Truy vấn dạng ~2~

• 3 l r ~(1 \le l \le r \le n)~: Truy vấn dạng ~3~

Output

Với mỗi truy vấn dạng ~3~, in ra một dòng gồm ~5~ số nguyên thuộc ~[0,1000000007)~, là kết quả của các phép tính.

Scoring

Subtask	Điểm	Ràng buộc
1	~8\%~	~N,Q \le 500~; không có truy vấn dạng ~2~
2	~8\%~	~N,Q \le 500~; có truy vấn dạng ~2~
3	~21\%~	~N,Q \le 50000~; không có truy vấn dạng ~2~
4	~21\%~	~N,Q \le 50000~; có truy vấn dạng ~2~
5	~21\%~	~N,Q \le 100000~; không có truy vấn dạng ~2~
6	~21\%~	~N,Q \le 100000~; có truy vấn dạng ~2~

Chú ý: Thí sinh không cần giải đúng với mọi ~K~ để được điểm dương. Chẳng hạn, để được tính điểm cho ~K=3~, thí sinh chỉ cần giải đúng với ~K=3~ trong mọi truy vấn ~3~. Cụ thể tỉ lệ điểm với giới hạn ~N,Q~ và giá trị ~K~ trả lời đúng được cố định như sau:

	~N,Q \le 500~	~N,Q \le 50000~	~N,Q \le 100000~
~k=0~	~4\%~	~4\%~	~4\%~
~k=1~	~4\%~	~6\%~	~6\%~
~k=2~	~4\%~	~12\%~	~12\%~
~k=3~	~2\%~	~8\%~	~8\%~
~k=4~	~2\%~	~12\%~	~12\%~

Ví dụ, nếu thí sinh trả lời đúng với ~N,Q \le 50000~ và ~k \in \{0;3\}~, sẽ được ~4\%+2\%+4\%+8\%~ số điểm của bài.

Với mỗi dòng trong đầu ra, thí sinh vẫn cần phải in ra đúng ~5~ số thuộc khoảng ~[0,1000000007)~ để được điểm.

Sample Input 1

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

Sample Output 1

1 20 400 8000 160000

Sample Input 2

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

Sample Output 2

1 10 100 1000 10000
6 87 1395 24507 463539

Sample Input 3

4 4 10
1 2 9 6
3 3 4
1 1 3 6
2 2 4 1
3 2 3

Sample Output 3

3 60 1242 26580 586482
3 166 10838 761344 55145522

Sample Input 4

4 4 3
4 8 6 7
3 3 4
3 2 3
1 2 4 2
3 2 4

Sample Output 4

3 35 437 5825 82097
3 37 491 6973 104723
6 156 4702 160452 5995894

Sample Input 5

10 10 10
6 12 10 1 5 13 15 2 1 1
2 7 9 8
1 2 10 15
1 2 8 1
1 7 9 9
3 5 9
1 2 6 12
2 9 10 3
3 3 5
2 5 6 8
3 1 3

Sample Output 5

15 46905 208478625 779393492 303109245
6 8880 17640600 3367720 431372103
6 14118 44289708 877035991 608288387