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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.math.BigInteger;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;
 
/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) throws IOException {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader sc = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task solver = new Task();
        solver.solve(1, sc, out);
        out.close();
    }
 
    static class Task {
    	public static final long Mod=(long) (1e9+7);
    	
    	public long quickPow(long x,long y) {
    		long res=1;
    		
    		while(y>0) {
    			if((y&1)==1)
    				res=res*x%Mod;
    			x=x*x%Mod;
    			y>>=1;
    		}
    		
    		return res;
    	}
    	
        public void solve(int testNumber, InputReader sc, PrintWriter out) throws IOException {
        	/*int exp=4;
        	long ans=5+quickPow(2,exp)*6l+quickPow(3,exp)*7+quickPow(4,exp)*8+quickPow(5,exp)*9+quickPow(6,exp)*10;
        	System.out.println(ans%Mod);*/
        	int n=sc.nextInt();
        	int m=sc.nextInt();
        	long[] A=new long[n+1];
        	
        	for(int i=1;i<=n;i++)
        		A[i]=sc.nextLong();
        	SegTree sgt=new SegTree(n,A);
        	sgt.build(1, 1, n);
        	
        	while(m-->0) {
        		char opt=sc.next().charAt(0);
        		int l=sc.nextInt();
        		int r=sc.nextInt();
        		int x=sc.nextInt();
        		
        		if(opt=='=') 
        			sgt.change(1, l, r, x);
        		else
        			out.println(sgt.getAns(l, r, x)%Mod);
        	}
        }
    }
    
    static class SegTree{
    	class Node{
    		int l;
    		int r;
    		long[] sum=new long[6];
    		long[] exp=new long[6];
            long tag;
            
            public Node(int l,int r) {
            	this.l=l;
            	this.r=r;
            	this.tag=-1;
            }
    	}
    	
    	public static final long Mod=(long) (1e9+7);
    	public Node[] t;
    	public long[] A;
    	
    	public SegTree(int n,long[] A) {
    		this.t=new Node[(n+10)<<2];
    		this.A=A;
    	}
    	
    	public long quickPow(long x,long y) {
    		long res=1;
    		
    		while(y>0) {
    			if((y&1)==1)
    				res=res*x%Mod;
    			x=x*x%Mod;
    			y>>=1;
    		}
    		
    		return res;
    	}
    	
    	public void pushDown(int p) {
    		if(t[p].tag!=-1) {
    			t[p*2].tag=t[p*2+1].tag=t[p].tag;
    			for(int i=0;i<=5;i++) {
    				t[p*2].sum[i]=t[p*2].exp[i]*t[p].tag%Mod;
    				t[p*2+1].sum[i]=t[p*2+1].exp[i]*t[p].tag%Mod;
    			}
    			t[p].tag=-1;
    		}
    	}
    	
    	public void pushUp(int p,boolean flag) {
    		for(int i=0;i<=5;i++) {
    			t[p].sum[i]=(t[p*2].sum[i]+t[p*2+1].sum[i])%Mod;
    			if(flag)
    				t[p].exp[i]=(t[p*2].exp[i]+t[p*2+1].exp[i])%Mod;
    		}
    	}
    	
    	public void build(int p,int l,int r) {
    		t[p]=new Node(l,r);
    		if(l==r) {
    			for(int i=0;i<=5;i++)
    				t[p].exp[i]=quickPow(l,i)%Mod;
    			for(int i=0;i<=5;i++)
    				t[p].sum[i]=t[p].exp[i]*A[l]%Mod;
    			return ;
    		}
    		int mid=(l+r)>>1;
    	    build(p*2,l,mid);
    	    build(p*2+1,mid+1,r);
    	    pushUp(p,true);
    	}
    	
    	public void change(int p,int l,int r,long val) {
    		if(t[p].l>=l&&t[p].r<=r) {
    			t[p].tag=val;
    			for(int i=0;i<=5;i++) {
    				t[p].sum[i]=t[p].exp[i]*val%Mod;
    			}
    			return ;
    		}
    		pushDown(p);
    		int mid=(t[p].l+t[p].r)>>1;
    	    if(l<=mid)
    	    	change(p*2,l,r,val);
    	    if(r>mid)
    	    	change(p*2+1,l,r,val);
    	    pushUp(p,false);
    	}
    	
    	public long ask(int p,int l,int r,int k) {
    		if(t[p].l>=l&&t[p].r<=r) 
    			return t[p].sum[k]%Mod;
    		pushDown(p);
    		long res=0;
    		int mid=(t[p].l+t[p].r)>>1;
    		if(l<=mid)
    			res+=ask(p*2,l,r,k);
    		if(r>mid)
    			res+=ask(p*2+1,l,r,k);
    		return res%Mod;
    	}
    	
    	public long getAns(int l,int r,int k) {
    		long temp=ask(1,l,r,0);
    		switch(k) {
    		case 0:
    			return ask(1,l,r,0);
    		case 1:
    			return ((ask(1,l,r,1)-(l-1)*temp%Mod+Mod)%Mod+Mod)%Mod;
    		case 2:
    			return ((ask(1,l,r,2)-2l*ask(1,l,r,1)*(l-1)%Mod+quickPow(l-1,2)*temp%Mod+Mod)%Mod+Mod)%Mod;
    		case 3:
    			return ((ask(1,l,r,3)-3l*ask(1,l,r,2)*(l-1)%Mod+3l*ask(1,l,r,1)*quickPow(l-1,2)%Mod-quickPow(l-1,3)*temp%Mod+Mod)%Mod+Mod)%Mod;
    		case 4:
    			return ((ask(1,l,r,4)-4l*ask(1,l,r,3)%Mod*(l-1)%Mod-4l*ask(1,l,r,1)%Mod*quickPow(l-1,3)%Mod+6l*ask(1,l,r,2)%Mod*quickPow(l-1,2)%Mod+temp*quickPow(l-1,4)%Mod+Mod)%Mod+Mod)%Mod;
    		case 5:
    			return ((ask(1,l,r,5)+5l*ask(1,l,r,1)*quickPow(l-1,4)%Mod-5l*ask(1,l,r,4)%Mod*(l-1)+10*ask(1,l,r,3)%Mod*quickPow(l-1,2)%Mod-10l*ask(1,l,r,2)%Mod*quickPow(l-1,3)%Mod-quickPow(l-1,5)*temp%Mod+Mod)%Mod+Mod)%Mod;	
    		}
    		return -1;
    	}
    }
 
    static class InputReader{
        StreamTokenizer tokenizer;
        public InputReader(InputStream stream){
            tokenizer=new StreamTokenizer(new BufferedReader(new InputStreamReader(stream)));
            tokenizer.ordinaryChars(33,126);
            tokenizer.wordChars(33,126);
        }
        public String next() throws IOException {
            tokenizer.nextToken();
            return tokenizer.sval;
        }
        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }
        public boolean hasNext() throws IOException {
            int res=tokenizer.nextToken();
            tokenizer.pushBack();
            return res!=tokenizer.TT_EOF;
        }
        
        public double nextDouble() throws NumberFormatException, IOException {
        	return Double.parseDouble(next());
        }
        
        public BigInteger nextBigInteger() throws IOException {
        	return new BigInteger(next());
        }
    }
}