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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int Mod = 1000000007;
struct AnsType {
  long long Sum[6];
};
AnsType operator+(AnsType A, AnsType B) {
  AnsType Ans;
  for (int i = 0; i <= 5; i++) {
    Ans.Sum[i] = A.Sum[i] + B.Sum[i];
    if (Ans.Sum[i] >= Mod) Ans.Sum[i] -= Mod;
  }
  return Ans;
}
int Get() {
  char c;
  while (c = getchar(), c < '0' || c > '9')
    ;
  int X = 0;
  while (c >= '0' && c <= '9') {
    X = X * 10 + c - 48;
    c = getchar();
  }
  return X;
}
void Output(int X) {
  int Len = 0, Data[10];
  while (X) {
    Data[Len++] = X % 10;
    X /= 10;
  }
  if (!Len) Data[Len++] = 0;
  while (Len--) putchar(Data[Len] + 48);
  putchar('\n');
}
long long Data[100000];
int Calc[100000][6];
int Left[262144], Right[262144], Flag[262144];
AnsType Value[262144];
void Build(int P, int L, int R) {
  Left[P] = L;
  Right[P] = R;
  Flag[P] = -1;
  if (L == R) {
    Value[P].Sum[0] = Data[L];
    for (int i = 1; i <= 5; i++)
      Value[P].Sum[i] = Value[P].Sum[i - 1] * L % Mod;
  } else {
    int Mid = (L + R) / 2;
    Build(P * 2, L, Mid);
    Build(P * 2 + 1, Mid + 1, R);
    Value[P] = Value[P * 2] + Value[P * 2 + 1];
  }
}
int F(long long N, int P) { return (N < 0) ? 0 : Calc[N][P]; }
void Update(int P) {
  if (Flag[P] == -1) return;
  for (int i = 0; i <= 5; i++) {
    Value[P].Sum[i] =
        (long long)Flag[P] * (F(Right[P], i) - F(Left[P] - 1, i)) % Mod;
    if (Value[P].Sum[i] < 0) Value[P].Sum[i] += Mod;
  }
  if (Left[P] != Right[P]) Flag[P * 2] = Flag[P * 2 + 1] = Flag[P];
  Flag[P] = -1;
}
void Cover(int P, int L, int R, int X) {
  Update(P);
  if (Left[P] == L && Right[P] == R) {
    Flag[P] = X;
    return;
  }
  int Mid = (Left[P] + Right[P]) / 2;
  if (R <= Mid)
    Cover(P * 2, L, R, X);
  else if (L > Mid)
    Cover(P * 2 + 1, L, R, X);
  else {
    Cover(P * 2, L, Mid, X);
    Cover(P * 2 + 1, Mid + 1, R, X);
  }
  Update(P * 2);
  Update(P * 2 + 1);
  Value[P] = Value[P * 2] + Value[P * 2 + 1];
}
AnsType Query(int P, int L, int R) {
  Update(P);
  if (Left[P] == L && Right[P] == R) return Value[P];
  int Mid = (Left[P] + Right[P]) / 2;
  if (R <= Mid) return Query(P * 2, L, R);
  if (L > Mid) return Query(P * 2 + 1, L, R);
  return Query(P * 2, L, Mid) + Query(P * 2 + 1, Mid + 1, R);
}
int main() {
  int N = Get(), M = Get();
  for (int i = 0; i < N; i++) Data[i] = Get();
  Build(1, 0, N - 1);
  static int C[6][6];
  for (int i = 0; i <= 5; i++)
    for (int j = 0; j <= i; j++)
      if (i == j || !j)
        C[i][j] = 1;
      else
        C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
  for (int i = 0; i < N; i++) {
    Calc[i][0] = 1;
    for (int j = 1; j <= 5; j++)
      Calc[i][j] = (long long)Calc[i][j - 1] * i % Mod;
    if (i)
      for (int j = 0; j <= 5; j++) {
        Calc[i][j] += Calc[i - 1][j];
        if (Calc[i][j] >= Mod) Calc[i][j] -= Mod;
      }
  }
  while (M--) {
    char c;
    while (c = getchar(), c != '=' && c != '?')
      ;
    int L = Get() - 1, R = Get() - 1, X = Get();
    if (c == '=')
      Cover(1, L, R, X);
    else {
      AnsType T = Query(1, L, R);
      int Delta = 1 - L;
      long long Ans = 0, S = 1;
      for (int i = 0; i <= X; i++) {
        Ans = (Ans + S * T.Sum[X - i] % Mod * C[X][i]) % Mod;
        if (Ans < 0) Ans += Mod;
        S = S * Delta % Mod;
        if (S < 0) S += Mod;
      }
      Output((int)Ans);
    }
  }
  return 0;
}