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 N = 1e5 + 3, Mod = 1e9 + 7;
int n, m, a[N], C[10][10];
int subsum[N << 3][6], tag[N << 3];
long long Psum[N][6], P[N][6];
inline void mod(int &x) {
  if (x >= Mod) x -= Mod;
}
inline void update(const int &k) {
  int lc = k << 1, rc = lc | 1;
  for (int i = 0; i <= 5; ++i)
    mod(subsum[k][i] = subsum[lc][i] + subsum[rc][i]);
}
inline void marktag(const int &k, const int &l, const int &r,
                    const long long &v) {
  tag[k] = v;
  for (int i = 0; i <= 5; ++i) {
    subsum[k][i] = v * (Psum[r][i] - Psum[l - 1][i]) % Mod;
    if (subsum[k][i] < 0) subsum[k][i] += Mod;
  }
}
inline void pushdown(const int &k, const int &l, const int &r, const int &mid) {
  if (tag[k] == -1) return;
  marktag(k << 1, l, mid, tag[k]);
  marktag(k << 1 | 1, mid + 1, r, tag[k]);
  tag[k] = -1;
}
inline int Query(const int &k, const int &l, const int &r, const int &x,
                 const int &y, const int &type) {
  if (l >= x && r <= y) return subsum[k][type];
  int mid = l + r >> 1, res;
  pushdown(k, l, r, mid);
  if (y <= mid)
    return Query(k << 1, l, mid, x, y, type);
  else if (x > mid)
    return Query(k << 1 | 1, mid + 1, r, x, y, type);
  else
    return mod(res = Query(k << 1, l, mid, x, y, type) +
                     Query(k << 1 | 1, mid + 1, r, x, y, type)),
           res;
}
inline void Modify(const int &k, const int &l, const int &r, const int &x,
                   const int &y, const int &v) {
  if (l >= x && r <= y) {
    marktag(k, l, r, v);
    return;
  }
  int mid = l + r >> 1;
  pushdown(k, l, r, mid);
  if (y <= mid)
    Modify(k << 1, l, mid, x, y, v);
  else if (x > mid)
    Modify(k << 1 | 1, mid + 1, r, x, y, v);
  else
    Modify(k << 1, l, mid, x, y, v), Modify(k << 1 | 1, mid + 1, r, x, y, v);
  update(k);
}
inline void Build(const int &k, const int &l, const int &r) {
  tag[k] = -1;
  if (l == r) {
    for (int j = 0; j <= 5; ++j) subsum[k][j] = P[l][j] * a[l] % Mod;
    return;
  }
  int mid = l + r >> 1;
  Build(k << 1, l, mid);
  Build(k << 1 | 1, mid + 1, r);
  update(k);
}
inline void Init() {
  for (int i = 0; i <= 5; ++i) {
    C[i][0] = 1;
    for (int j = 1; j <= i; ++j) C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
  }
  for (int i = 1; i <= n; ++i) {
    long long tmp = 1;
    for (int j = 0; j <= 5; ++j) {
      Psum[i][j] = (Psum[i - 1][j] + (P[i][j] = tmp)) % Mod;
      tmp = tmp * i % Mod;
    }
  }
  Build(1, 1, n);
}
char ch, type;
inline int read() {
  while (ch = getchar(), ch < '0' || ch > '9')
    ;
  int res = ch - 48;
  while (ch = getchar(), ch >= '0' && ch <= '9') res = res * 10 + ch - 48;
  return res;
}
int main() {
  n = read();
  m = read();
  for (int i = 1; i <= n; ++i) a[i] = read();
  Init();
  while (m--) {
    while (type = getchar(), type != '?' && type != '=')
      ;
    if (type == '=') {
      int l = read(), r = read(), v = read();
      Modify(1, 1, n, l, r, v);
    } else {
      int l = read(), r = read(), v = read(), ans = 0, sgn = 1, tmp, L = 1;
      for (int i = v; i >= 0; --i) {
        tmp = (long long)C[v][i] * Query(1, 1, n, l, r, i) % Mod * L % Mod;
        ans = (ans + tmp * sgn) % Mod;
        if (ans < 0) ans += Mod;
        L = (long long)L * (l - 1) % Mod;
        sgn = -sgn;
      }
      printf("%d\n", ans);
    }
  }
  return 0;
}