## 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 a

_{x} and a

_{y} inclusive. In other words, do transformation a

_{k}<---a

_{k}+c, k = x,x+1,…,y.

Operation 2: Multiply c to each number between a

_{x} and a

_{y} inclusive. In other words, do transformation a

_{k}<---a

_{k}×c, k = x,x+1,…,y.

Operation 3: Change the numbers between a

_{x} and a

_{y} 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 a

_{x} and a

_{y} 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