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 练习splay代替线段树
###cdoe
1 
