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.*;
import java.util.*;
import java.math.*;
import java.util.concurrent.*;

public final class more_queries
{
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	static FastScanner sc=new FastScanner(br);
    static PrintWriter out=new PrintWriter(System.out);
	static Random rnd=new Random();
	static int[][] c;
	static int maxn=6;
	static int[][] pre,tree,lazy;
	static int n,q;
	static long mod=(long)(1e9+7);
	static int[] a;
	
	static void build()
	{
		pre=new int[maxn][n];
		
		for(int i=0;i<maxn;i++)
		{
			for(int j=0;j<n;j++)	
			{
				int now=pow(j+1,i);
				
				if(j>=1)
				{
					now=add(now,pre[i][j-1]);
				}
				
				pre[i][j]=now;
			}
		}
		
		c=new int[maxn][maxn];c[0][0]=1;
		
		for(int i=1;i<maxn;i++)
		{
			c[i][0]=1;
			
			for(int j=1;j<=i;j++)
			{
				c[i][j]=add(c[i-1][j],c[i-1][j-1]);
			}
		}
	}
	
	static int add(long a,long b)
	{
		long ret=a+b;
		
		if(ret>=mod)
		{
			ret%=mod;
		}
		
		return (int)ret;
	}
	
	static int mul(long a,long b)
	{
		long ret=a*b;
		
		if(ret>=mod)
		{
			ret%=mod;
		}
		
		return (int)ret;
	}
	
	static int pow(int a,long b)
	{
		int x=1,y=a;
		
		while(b>0)
		{	
			if(b%2==1)
			{
				x=mul(x,y);
			}
			
			y=mul(y,y);b=b/2;
		}
		
		return x;
	}
	
	static void build(int idx,int node,int s,int e)
	{
		if(s>e)
		{
			return;
		}
		
		if(s==e)
		{
			tree[idx][node]=mul(a[s],get(idx,s,s));
		}
		
		else
		{
			int mid=(s+e)>>1;
			
			build(idx,node<<1,s,mid);build(idx,node<<1|1,mid+1,e);
			
			tree[idx][node]=add(tree[idx][node<<1],tree[idx][node<<1|1]);
		}
	}
	
	static int get(int dim,int l,int r)
	{
		int val1=pre[dim][r],val2=(l-1<0?0:pre[dim][l-1]);
		
		int ret=add(val1,add(-val2,mod));
		
		return ret;
	}
	
	static void range_update(int idx,int node,int s,int e,int l,int r,int val)
	{
		if(lazy[idx][node]!=-1)
		{
			tree[idx][node]=mul(lazy[idx][node],get(idx,s,e));
			
			if(s!=e)
			{
				lazy[idx][node<<1]=lazy[idx][node];
				
				lazy[idx][node<<1|1]=lazy[idx][node];
			}
			
			lazy[idx][node]=-1;
		}
		
		if(s>e || l>e || r<s)
		{
			return;
		}
		
		if(l<=s && r>=e)
		{
			tree[idx][node]=mul(val,get(idx,s,e));
			
			if(s!=e)
			{
				lazy[idx][node<<1]=val;lazy[idx][node<<1|1]=val;
			}
		}
		
		else
		{
			int mid=(s+e)>>1;
			
			range_update(idx,node<<1,s,mid,l,r,val);range_update(idx,node<<1|1,mid+1,e,l,r,val);
			
			tree[idx][node]=add(tree[idx][node<<1],tree[idx][node<<1|1]);
		}
	}
	
	static void update(int l,int r,int x)
	{
		for(int i=0;i<maxn;i++)
		{
			range_update(i,1,0,n-1,l,r,x);
		}
	}
	
	static int lazy_query(int idx,int node,int s,int e,int l,int r)
	{
		if(lazy[idx][node]!=-1)
		{
			tree[idx][node]=mul(lazy[idx][node],get(idx,s,e));
			
			if(s!=e)
			{
				lazy[idx][node<<1]=lazy[idx][node];
				
				lazy[idx][node<<1|1]=lazy[idx][node];
			}
			
			lazy[idx][node]=-1;
		}
		
		if(s>e || l>e || r<s)
		{
			return 0;
		}
		
		if(l<=s && r>=e)
		{
			return tree[idx][node];
		}
		
		else
		{
			int mid=(s+e)>>1;
			
			return add(lazy_query(idx,node<<1,s,mid,l,r),lazy_query(idx,node<<1|1,mid+1,e,l,r));
		}
	}
	
	static int query(int l,int r,int k)
	{
		int ret=0,curr1=(k%2==0?1:(int)(-1+mod));
		
		for(int i=0;i<=k;i++)
		{
			int curr2=pow(l,k-i);
			
			int zz=mul(curr1,curr2);
			
			int now1=c[k][i],now2=lazy_query(i,1,0,n-1,l,r);
			
			int tot=mul(now1,zz);tot=mul(tot,now2);
			
			curr1*=-1;curr1=add(curr1,mod);
			
			ret=add(ret,tot);
		}
		
		return ret;
	}
	
    public static void main(String args[]) throws Exception
    {
		n=sc.nextInt();q=sc.nextInt();build();
		
		a=new int[n];
		
		for(int i=0;i<n;i++)
		{
			a[i]=sc.nextInt();
		}
		
		tree=new int[maxn][4*n];lazy=new int[maxn][4*n];
		
		for(int i=0;i<maxn;i++)
		{
			build(i,1,0,n-1);
			
			Arrays.fill(lazy[i],-1);
		}
		
//		out.println(get(1,0,n-1));
		
		while(q>0)
		{
			char ch=sc.next().charAt(0);
			
			if(ch=='=')
			{
				int l=sc.nextInt()-1,r=sc.nextInt()-1,x=sc.nextInt();
				
				update(l,r,x);
			}
			
			else
			{
				int l=sc.nextInt()-1,r=sc.nextInt()-1,k=sc.nextInt();
				
				out.println(query(l,r,k));
			}
			
			q--;
		}

		out.close();
    }
}
class FastScanner
{
    BufferedReader in;
    StringTokenizer st;

    public FastScanner(BufferedReader in) {
        this.in = in;
    }
	
    public String nextToken() throws Exception {
        while (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(in.readLine());
        }
        return st.nextToken();
    }
	
	public String next() throws Exception {
		return nextToken().toString();
	}
	
    public int nextInt() throws Exception {
        return Integer.parseInt(nextToken());
    }

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

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