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 double PI = 2.0 * acos(0.0);
const double EPS = 1e-6;
int a[100005];
inline long long ADD(long long aa, long long bb) {
  return (aa + bb) % 1000000007LL;
}
inline long long SUB(long long aa, long long bb) {
  return (aa - bb + 1000000007LL) % 1000000007LL;
}
inline long long MUL(long long aa, long long bb) {
  return aa * bb % 1000000007LL;
}
struct SegmentTree {
  long long cover[100005 * 4], sum[100005 * 4], pow[100005], spow[100005];
  void init(int id, int L, int R) {
    cover[id] = -1;
    if (L == R) {
      sum[id] = MUL(a[L], pow[L]);
      return;
    }
    int mid = (L + R) >> 1;
    init(((id)*2), L, mid);
    init(((id)*2 + 1), mid + 1, R);
    sum[id] = ADD(sum[((id)*2)], sum[((id)*2 + 1)]);
  }
  void push(int id, int L, int R) {
    if (cover[id] == -1) return;
    cover[((id)*2)] = cover[((id)*2 + 1)] = cover[id];
    int mid = (L + R) >> 1;
    sum[((id)*2)] = MUL(cover[id], SUB(spow[mid], spow[L - 1]));
    sum[((id)*2 + 1)] = MUL(cover[id], SUB(spow[R], spow[mid]));
    cover[id] = -1;
  }
  void pull(int id) { sum[id] = ADD(sum[((id)*2)], sum[((id)*2 + 1)]); }
  long long query(int id, int L, int R, int a, int b) {
    if (b < L || a > R) return 0LL;
    if (a <= L && R <= b) return sum[id];
    int mid = (L + R) >> 1;
    push(id, L, R);
    long long res = ADD(query(((id)*2), L, mid, a, b),
                        query(((id)*2 + 1), mid + 1, R, a, b));
    pull(id);
    return res;
  }
  void set(int id, int L, int R, int a, int b, int x) {
    if (b < L || a > R) return;
    if (a <= L && R <= b) {
      cover[id] = x;
      sum[id] = MUL(x, SUB(spow[R], spow[L - 1]));
      return;
    }
    int mid = (L + R) >> 1;
    push(id, L, R);
    set(((id)*2), L, mid, a, b, x);
    set(((id)*2 + 1), mid + 1, R, a, b, x);
    pull(id);
  }
} seg[6];
long long C[8][8];
void precall() {
  for (int i = 0; i < 8; i++)
    for (int j = C[i][0] = 1; j <= i; j++)
      C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
  for (int j = 0; j < 100005; j++) seg[0].pow[j] = 1LL;
  for (int k = 1; k <= 5; k++)
    for (int j = 0; j < 100005; j++) seg[k].pow[j] = MUL(seg[k - 1].pow[j], j);
  for (int k = 0; k <= 5; k++)
    for (int j = 1; j < 100005; j++)
      seg[k].spow[j] = ADD(seg[k].spow[j - 1], seg[k].pow[j]);
}
int main() {
  precall();
  int n, m;
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d", a + i);
  for (int k = 0; k <= 5; k++) seg[k].init(1, 1, n);
  while (m--) {
    char op[2];
    int l, r, x;
    scanf("%s %d %d %d", op, &l, &r, &x);
    if (op[0] == '=') {
      for (int k = 0; k <= 5; k++) seg[k].set(1, 1, n, l, r, x);
    } else {
      long long res = 0LL;
      for (int k = x; k >= 0; k--) {
        if ((x - k) & 1)
          res = SUB(res, MUL(MUL(C[x][k], seg[x - k].pow[l - 1]),
                             seg[k].query(1, 1, n, l, r)));
        else
          res = ADD(res, MUL(MUL(C[x][k], seg[x - k].pow[l - 1]),
                             seg[k].query(1, 1, n, l, r)));
      }
      printf("%I64d\n", res);
    }
  }
  return 0;
}