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.util.Scanner;
public class Main {
	static int INF=1000000007;
	static int  MAXN= 100005;
	static long sum[][]=new long[6][MAXN<<2];
	static long col[]=new long[MAXN<<2];
	static long data[][]=new long[6][MAXN];
	static long C[][]=new long[6][6];
	static long POW[][]=new long[MAXN][6];
	
	
	static node addedge(node a,node b)
	{
	      int i;
	      for (i=0;i<6;i++) a.a[i]=(a.a[i]+b.a[i])%INF;
	      return a;
	}
	static void PreWork()
	{
	      int i,j;
	      long  x;
	   
	      POW[0][0]=1;
	      for (i=1;i<=100000;i++)
	      {
	             x=1;
	             for (j=0;j<6;j++) {POW[i][j]=x;data[j][i]=(data[j][i-1]+x)%INF;x=(x*i)%INF;}
	      }
	      for (i=0;i<6;i++) C[i][0]=C[i][i]=1;
	      for (i=1;i<6;i++)
	         for (j=1;j<6;j++)
	           C[i][j]=C[i-1][j-1]+C[i-1][j];
	      return ;
	}
	static void PushDown(int l,int r,int now)
	{
	      int i,mid=(l+r)/2;
	      long  x;
	      if (col[now]<0) return;
	      col[now<<1]=col[(now<<1)|1]=col[now];
	      for (i=0;i<6;i++)
	      {
	              x=data[i][mid]-data[i][l-1];
	              if (x<0) x=INF+x;
	              sum[i][now<<1]=(col[now]*x)%INF;
	              x=data[i][r]-data[i][mid];
	              if (x<0) x=INF+x;
	              sum[i][(now<<1)|1]=(col[now]*(data[i][r]-data[i][mid]))%INF;
	      }
	      col[now]=-1;
	      return;
	}
	static void update(int L,int R,int c,int l,int r,int now)
	{
	      int i;
	      long  x;
	      if (L<=l && R>=r)
	      {
	             col[now]=c;
	             for (i=0;i<6;i++)
	             {
	                    x=data[i][r]-data[i][l-1];
	                    if (x<0) x=INF+x;
	                    sum[i][now]=(c*x)%INF;
	             }
	             return;
	      }
	      PushDown(l,r,now);
	      int mid=(l+r)>>1;
	      if (L<=mid) update(L,R,c,l,mid,now<<1);
	      if (mid<R)  update(L,R,c,mid+1,r,(now<<1)|1);
	      for (i=0;i<6;i++) sum[i][now]=(sum[i][now<<1]+sum[i][(now<<1)|1])%INF;
	      return;
	}
	static node query(int L,int R,int l,int r,int now)
	{
	      node h=new node();
	      if (L<=l && R>=r)
	      {
	             for (int i=0;i<6;i++) h.a[i]=sum[i][now];
	             return h;
	      }
	      PushDown(l,r,now);
	      int mid=(l+r)>>1;
	     
	      if (L<=mid) h=addedge(h,query(L,R,l,mid,now<<1));
	      if (mid<R)  h=addedge(h,query(L,R,mid+1,r,(now<<1)|1));
	      return h;
	}
	 static long getans(node h,long L,int k)
	{
	      int i;
	      long  t,ans=0;
	      for (i=0;i<=k;i++)
	      {
	             t=(C[k][i]*h.a[i])%INF;
	             t=(t*POW[(int) (L-1)][k-i])%INF;
	             if (((k-i)%2)!=0) t=-t;
	             ans=(ans+t)%INF;
	      }
	      return (ans+INF)%INF;
	}
public static void main(String[] args) {
	Scanner scan=new Scanner(System.in);
	
	      int i,n,m,x,y,z;
	      String c;
	      PreWork();
	      n=scan.nextInt();
	      m=scan.nextInt();
	      {
	              
	    	  
	              for (i=1;i<=n;i++)
	              {
	                    x=scan.nextInt();
	                     update(i,i,x,1,n,1);
	              }
	              while (m-->0)
	              {
	                     do { c=scan.next(); } while(!c.equals("=") && !c.equals("?"));
	                     x=scan.nextInt();
	                     y=scan.nextInt();
	                     z=scan.nextInt();
	                     if (c.equals("?"))  System.out.println(getans(query(x,y,1,n,1),x,z));
	                        else update(x,y,z,1,n,1);
	              }
	      }

	
	
	
	
}
}
class node
{
    long a[]=new long[6];
};