Transformation

Source: HDU

Version: Phuoc Hung OJ Extended

Problem Statement

Start with an all-zero array. Support range add, range multiply, range assignment, and range sum of powers $p=1,2,3$ modulo 10007.

Input

The first line contains $n,m$. Exactly $m$ lines op l r c follow: operation 1 adds $c$, operation 2 multiplies by $c$, operation 3 assigns $c$, and operation 4 uses $c=p\in\{1,2,3\}$ to query the sum of $p$-th powers modulo $10007$. The original HDU 0 0 sentinel is removed in this PHOJ version.

Output

For each type-4 operation print the answer modulo $10007$.

Subtasks

• Subtask 1 (20%): size and operation count at most 30; all other validity conditions are unchanged.

• Subtask 2 (30%): size and operation count at most 3000; all other validity conditions are unchanged.

• Subtask 3 (50%): full constraints:

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

• $1\le c\le10000$

• $1\le p\le3$

Examples

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

Explanation

After assignment and addition, the array is [0,4,11,11,7]; the square sum is 307 modulo 10007. After multiplying [2,5] by 8, the cube-sum query on [3,5] gives 7489.