# hdu4578

###name
Transformation

###description
Yuanfang is puzzled with the question below:
There are n integers, \$a_1, a_2, …, a_n\$. The initial values of them are 0. There are four kinds of operations.
Operation 1: Add c to each number between ax and ay inclusive. In other words, do transformation \$a_k=a_k+c\$, k = x,x+1,…,y.
Operation 2: Multiply c to each number between ax and ay inclusive. In other words, do transformation \$a_k=a_k×c\$, k = x,x+1,…,y.
Operation 3: Change the numbers between ax and ay to c, inclusive. In other words, do transformation \$a_k=c\$, k = x,x+1,…,y.
Operation 4: Get the sum of p power among the numbers between ax and ay inclusive. In other words, get the result of \$a_x^p+a_{x+1}^p+…+a_y^p\$.
Yuanfang has no idea of how to do it. So he wants to ask you to help him.

###input
There are no more than 10 test cases.
For each case, the first line contains two numbers n and m, meaning that there are n integers and m operations. 1 <= n, m <= 100,000.
Each the following m lines contains an operation. Operation 1 to 3 is in this format: “1 x y c” or “2 x y c” or “3 x y c”. Operation 4 is in this format: “4 x y p”. (1 <= x <= y <= n, 1 <= c <= 10,000, 1 <= p <= 3)
The input ends with 0 0.

###output
For each operation 4, output a single integer in one line representing the result. The answer may be quite large. You just need to calculate the remainder of the answer when divided by 10007.

###sample input
5 5
3 3 5 7
1 2 4 4
4 1 5 2
2 2 5 8
4 3 5 3
0 0

###sample output
307
7489

###tutorial

###cdoe