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;
inline void read(int &x) {
  int v = 0, f = 1;
  char c = getchar();
  while (!isdigit(c) && c != '-') c = getchar();
  if (c == '-')
    f = -1;
  else
    v = (c & 15);
  while (isdigit(c = getchar())) v = (v << 1) + (v << 3) + (c & 15);
  x = v * f;
}
inline void read(long long &x) {
  long long v = 0ll, f = 1ll;
  char c = getchar();
  while (!isdigit(c) && c != '-') c = getchar();
  if (c == '-')
    f = -1;
  else
    v = (c & 15);
  while (isdigit(c = getchar())) v = (v << 1) + (v << 3) + (c & 15);
  x = v * f;
}
inline void readc(char &x) {
  char c;
  while (((c = getchar()) == ' ') || c == '\n')
    ;
  x = c;
}
const int mod = 1e9 + 7;
int n, m, i, j, a[100005], c[6][6], pw[6][100005], pre[6][100005];
struct seg {
  int s[6];
} tr[400005];
int tag[400005];
seg merge(seg x, seg y) {
  seg z;
  int i;
  for (((i)) = (0); ((i)) <= (((int)(6)) - 1); ((i))++) {
    z.s[i] = (x.s[i] + y.s[i]) % mod;
  }
  return z;
}
void pushup(int x) { tr[x] = merge(tr[x + x], tr[x + x + 1]); }
void upd(int x, int l, int r, int y) {
  tag[x] = y;
  int i;
  for (((i)) = (0); ((i)) <= (((int)(6)) - 1); ((i))++) {
    tr[x].s[i] = 1ll * (pre[i][r] - pre[i][l - 1] + mod) * y % mod;
  }
}
void pushdo(int x, int l, int r) {
  int mid = (l + r) / 2;
  if (tag[x] != -1) {
    upd(x + x, l, mid, tag[x]);
    upd(x + x + 1, mid + 1, r, tag[x]);
    tag[x] = -1;
  }
}
void build(int x, int l, int r) {
  tag[x] = -1;
  if (l == r) {
    int i;
    for (((i)) = (0); ((i)) <= (((int)(6)) - 1); ((i))++)
      tr[x].s[i] = 1ll * a[l] * pw[i][l] % mod;
    return;
  }
  int mid = (l + r) / 2;
  build(x + x, l, mid);
  build(x + x + 1, mid + 1, r);
  pushup(x);
}
void update(int x, int l, int r, int ql, int qr, int y) {
  if (ql <= l && r <= qr) {
    upd(x, l, r, y);
    return;
  }
  int mid = (l + r) / 2;
  pushdo(x, l, r);
  if (ql <= mid) update(x + x, l, mid, ql, qr, y);
  if (qr > mid) update(x + x + 1, mid + 1, r, ql, qr, y);
  pushup(x);
}
seg query(int x, int l, int r, int ql, int qr) {
  if (ql <= l && r <= qr) {
    return tr[x];
  }
  int mid = (l + r) / 2;
  pushdo(x, l, r);
  if (qr <= mid) return query(x + x, l, mid, ql, qr);
  if (ql > mid) return query(x + x + 1, mid + 1, r, ql, qr);
  return merge(query(x + x, l, mid, ql, qr),
               query(x + x + 1, mid + 1, r, ql, qr));
}
int main() {
  c[0][0] = 1;
  for (((i)) = (1); ((i)) <= ((5)); ((i))++) {
    c[i][0] = 1;
    for (((j)) = (1); ((j)) <= ((i)); ((j))++) {
      c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
    }
  }
  read(n);
  read(m);
  for (((i)) = (1); ((i)) <= ((n)); ((i))++) pw[0][i] = 1;
  pw[0][0] = 1;
  for (((j)) = (1); ((j)) <= ((5)); ((j))++)
    for (((i)) = (1); ((i)) <= ((n)); ((i))++)
      pw[j][i] = 1ll * pw[j - 1][i] * i % mod;
  for (((j)) = (0); ((j)) <= (((int)(6)) - 1); ((j))++)
    for (((i)) = (1); ((i)) <= ((n)); ((i))++)
      pre[j][i] = (pre[j][i - 1] + pw[j][i]) % mod;
  for (((i)) = (1); ((i)) <= ((n)); ((i))++) read(a[i]);
  build(1, 1, n);
  while (m--) {
    char op;
    readc(op);
    if (op == '=') {
      int l, r, x;
      read(l);
      read(r);
      read(x);
      update(1, 1, n, l, r, x);
    } else {
      int l, r, x;
      read(l);
      read(r);
      read(x);
      seg res = query(1, 1, n, l, r);
      int ans = 0;
      for (((i)) = (0); ((i)) <= (((int)(x + 1)) - 1); ((i))++) {
        int t = 1ll * pw[x - i][l - 1] * res.s[i] % mod * c[x][i] % mod;
        if ((x - i) & 1)
          ans = (ans - t + mod) % mod;
        else
          ans = (ans + t) % mod;
      }
      printf("%d\n", ans);
    }
  }
  return 0;
}