Biến đổi (Transformation)

Nguồn: HDU

Phiên bản: Phước Hưng OJ Extended

Đề bài

Ban đầu có $n$ số đều bằng 0. Có bốn thao tác: cộng $c$ trên đoạn, nhân $c$ trên đoạn, gán $c$ trên đoạn, hoặc hỏi tổng lũy thừa bậc $p\in\{1,2,3\}$ trên đoạn modulo 10007.

Input

Dòng đầu chứa $n,m$. Sau đó có đúng $m$ thao tác, mỗi dòng gồm op l r c:

• op = 1: cộng $c$ vào đoạn.
• op = 2: nhân đoạn với $c$.
• op = 3: gán đoạn bằng $c$.
• op = 4: khi đó $c=p\in\{1,2,3\}$, hỏi $\sum a_i^p$ trên đoạn modulo $10007$.

Sentinel 0 0 của đề gốc HDU không xuất hiện trong phiên bản PHOJ.

Output

Mỗi thao tác loại 4 in đáp án modulo $10007$.

Subtask

• Subtask 1 (20%): $n$ và số thao tác không vượt 30; các điều kiện còn lại giữ như đề đầy đủ.

• Subtask 2 (30%): $n$ và số thao tác không vượt 3000; các điều kiện còn lại giữ như đề đầy đủ.

• Subtask 3 (50%): toàn bộ giới hạn:

• $1\le n,m\le10^5$

• $1\le c\le10000$

• $1\le p\le3$

Ví dụ

Input

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

Output

307
7489

Giải thích

Sau gán và cộng, mảng là [0,4,11,11,7]; tổng bình phương là 307 modulo 10007. Sau phép nhân 8 trên [2,5], truy vấn bậc 3 trên [3,5] cho 7489.