Problem: You've got an array, consisting of n integers: a1, a2, ..., an. Your task is to quickly run the queries of two types:

  1. Assign value x to all elements from l to r inclusive. After such query the values of the elements of array al, al + 1, ..., ar become equal to x.
  2. Calculate and print sum <image>, where k doesn't exceed 5. As the value of the sum can be rather large, you should print it modulo 1000000007 (109 + 7).

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 105), showing, how many numbers are in the array and the number of queries, correspondingly. The second line contains n integers: a1, a2, ..., an (0 ≤ ai ≤ 109) — the initial values of the array elements.

Then m queries follow, one per line:

  1. The assign query has the following format: "<image>", (1 ≤ l ≤ r ≤ n; 0 ≤ x ≤ 109).
  2. The query to calculate the sum has the following format: "<image>", (1 ≤ l ≤ r ≤ n; 0 ≤ k ≤ 5).



All numbers in the input are integers.

Output

For each query to calculate the sum print an integer — the required sum modulo 1000000007 (109 + 7).

Examples

Input

4 5
5 10 2 1
? 1 2 1
= 2 2 0
? 2 4 3
= 1 4 1
? 1 4 5


Output

25
43
1300


Input

3 1
1000000000 1000000000 1000000000
? 1 3 0


Output

999999986

Solution (in JAVA):

Solution:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.HashMap;
import java.util.StringTokenizer;


public class E {	
	BufferedReader reader;
    StringTokenizer tokenizer;
    PrintWriter out;
    
    long MOD = (long) (1e9 + 7);
    
    public static long power(long base, long exponent, long mod) {
		if (base >= mod)
			base %= mod;
		if (exponent == 0)
			return 1 % mod;
		long result = power(base, exponent >> 1, mod);
		result = result * result % mod;
		if ((exponent & 1) != 0)
			result = result * base % mod;
		return result;
	}
    public static long modadd(long base, long add, long mod){
    	long result = base + add;
    	result = result % mod;
    	while( result < 0)
    		result += mod;
    	return result;
    }
    
    public class SegmentTree{
    	int size;
    	int length;
    	long[][] power;
    	long[][] sumpower;
    	long[][] values;
    	long[] newvalues;
    	
    	public SegmentTree(int[] a){
    		size =  Integer.highestOneBit(a.length)*4;
    		length = a.length;
    		power = new long[6][size];
    		values = new long[6][size];
    		newvalues = new long[size];
    		Arrays.fill(power[0], 1);
    		for(int i = 1; i < 6; i++){
    			for(int j = 0; j < size; j++){
    				power[i][j] = power[i-1][j] * (j+1) % MOD;
    			}
    		}
    		sumpower = new long[6][size+1];
    		for (int i = 0; i < 6; i++) {
                for (int j = 0; j < size; j++) {
                	sumpower[i][j + 1] = (sumpower[i][j] + power[i][j]) % MOD;                    
                }
            }
    		for(int i = 0; i < size; i++){
    			newvalues[i] = -1;
    		}
    		init(0, 0, a.length-1, a);
    	}
    	public long query(int l, int r, int k){
    		return query(0, 0, length-1, l, r, k);
    	}
    	
    	public long query(int node, int b, int e, int i, int j, int k){
    		if( i > e || j < b ){
    			return -1;
    		}
    		else if( b >= i && e <= j ){
    			int constant = i;
    			
    			if( k == 0){
    				return values[0][node];
    			}
    			if( k == 1){
    				long result = values[1][node];
    				result = modadd(result, -1 * ((values[0][node] * constant) % MOD), MOD);
    				return result;
    			}
    			if( k == 2){
    				long result = values[2][node];
    				result = modadd(result, -2 * ((values[1][node] * constant) % MOD), MOD);
    				result = modadd(result, (values[0][node] * power(constant, 2, MOD)) % MOD, MOD);
    				return result;
    			}
    			if( k == 3){
    				long result = values[3][node];
    				result = modadd(result, -3 * ((values[2][node] * constant) % MOD), MOD);
    				result = modadd(result, 3 * (values[1][node] * power(constant, 2, MOD)) % MOD, MOD);
    				result = modadd(result, -1 * (values[0][node] * power(constant, 3, MOD)) % MOD, MOD);
    				return result;
    			}
    			if( k == 4){
    				long result = values[4][node];
    				result = modadd(result, -4 * ((values[3][node] * constant) % MOD), MOD);
    				result = modadd(result, 6 * ((values[2][node] * power(constant, 2, MOD)) % MOD), MOD);
    				result = modadd(result, -4 * ((values[1][node] * power(constant, 3, MOD)) % MOD), MOD);
    				result = modadd(result, 1 * (values[0][node] * power(constant, 4, MOD)) % MOD, MOD);
    				return result;
    			}
    			if( k == 5){
    				long result = values[5][node];
    				result = modadd(result, -5 * ((values[4][node] * constant) % MOD), MOD);
    				result = modadd(result, 10 * ((values[3][node] * power(constant, 2, MOD)) % MOD), MOD);
    				result = modadd(result, -10 * ((values[2][node] * power(constant, 3, MOD)) % MOD), MOD);
    				result = modadd(result, 5 * ((values[1][node] * power(constant, 4, MOD)) % MOD), MOD);
    				result = modadd(result, -1 * ((values[0][node] * power(constant, 5, MOD)) % MOD), MOD);
    				return result;
    			}
    			return values[0][node];
    		}
    		int mid = (b+e)/2;
    		
    		if( newvalues[node] != -1){
    			newvalues[node*2+1] = newvalues[node];
    			newvalues[node*2+2] = newvalues[node];
    			apply(node*2+1, b, mid);
    			apply(node*2+2, mid+1, e);
    			newvalues[node] = -1;
    		}
    		
    		
    		long p1 = query(2*node+1, b, mid, i, j, k);
    		long p2 = query(2*node+2, mid+1, e, i, j, k);
    		if(p1 == -1)
    			return p2;
    		if(p2 == -1)
    			return p1;
    		return (p1 + p2) % MOD;
    	}
    	
    	public void init(int node, int b, int e, int[] a){
    		if( b == e){
    			for(int i = 0; i < 6; i++){
    				values[i][node] = (power[i][b] * a[b]) % MOD;
    			} 
    		}
    		else{
    			int mid = (b+e)/2;
    			init(node*2+1, b, mid, a);
    			init(node*2+2, mid+1, e, a);
    			for(int i = 0; i < 6; i++){
    				values[i][node] = (values[i][node*2+1] + values[i][node*2+2]) % MOD;
    			}
    		}
    	}
    	
    	public void apply(int node, int left, int right){
    		for(int i = 0; i < 6; i++){
    			values[i][node] = ((sumpower[i][right+1] - sumpower[i][left]) * newvalues[node]) % MOD;
    			while( values[i][node] < 0)
    				values[i][node] += MOD;
    		}
    	}
    	
    	public void update(int node, int b, int e, int i, int j, long x){
    		if( i > e || j < b ){
    			return;
    		}
    		else if( b >= i && e <= j ){
    			newvalues[node] = x;
    			apply(node, b, e);
    			return;
    		}    		
    		int mid = (b+e)/2;    		
    		if( newvalues[node] != -1 ){
    			newvalues[node*2+1] = newvalues[node];
    			newvalues[node*2+2] = newvalues[node];
    			apply(node*2+1, b, mid);
    			apply(node*2+2, mid+1, e);    			
    			newvalues[node] = -1;
    		}
    		
    		update(node*2+1, b, mid, i, j, x);
    		update(node*2+2, mid+1, e, i, j, x);
    		for(int k = 0; k < 6; k++){
				values[k][node] = (values[k][node*2+1] + values[k][node*2+2]) % MOD;
			}    		
    	}
    	
    	public void update(int l, int r, long x){
    		update(0, 0, length-1, l, r, x);
    	}
    }
    
	public void solve() throws IOException {
		int N = nextInt();
		int M = nextInt();
		int[] a = new int[N];
		for(int i = 0; i < N; i++){
			a[i] = nextInt();
		}
		SegmentTree tree = new SegmentTree(a);
		for(int i = 0; i < M; i++){
			char op = (char) reader.read();
			if( op == '?' ){
				out.println(  tree.query( nextInt()-1, nextInt()-1, nextInt() ) );
			}
			else{
				tree.update(nextInt()-1, nextInt()-1, nextLong());
			}
		}
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		new E().run();
	}
	
	public void run() {
        try {
            reader = new BufferedReader(new InputStreamReader(System.in));
            tokenizer = null;
            out = new PrintWriter(System.out);
            solve();
            reader.close();
            out.close();
        } catch (Exception e) {
            e.printStackTrace();
            System.exit(1);
        }
    }

    int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

    double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }

    String nextToken() throws IOException {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(reader.readLine());
        }
        return tokenizer.nextToken();
    }

}