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 coef[6][6] = {{1, 0, 0, 0, 0, 0}, {1, 1, 0, 0, 0, 0},
                        {1, 2, 1, 0, 0, 0}, {1, 3, 3, 1, 0, 0},
                        {1, 4, 6, 4, 1, 0}, {1, 5, 10, 10, 5, 1}};
const int DIM = 100005;
const int MOD = 1e9 + 7;
int lzy[DIM * 4], sgt[6][DIM * 4], psm[6][DIM], arr[DIM];
int pwr(int x, int y) {
  int ans = 1;
  x = (x % MOD + MOD) % MOD;
  for (int i = 1; i <= y; ++i) ans = 1LL * ans * x % MOD;
  return ans;
}
void updateLazy(int nd, int le, int ri) {
  if (lzy[nd] != -1) {
    for (int k = 0; k <= 5; ++k)
      sgt[k][nd] = 1LL * lzy[nd] * (psm[k][ri] - psm[k][le - 1] + MOD) % MOD;
    if (le != ri) lzy[nd * 2] = lzy[nd * 2 + 1] = lzy[nd];
    lzy[nd] = -1;
  }
}
void updateNode(int nd, int le, int ri) {
  for (int k = 0; k <= 5; ++k)
    sgt[k][nd] = (sgt[k][nd * 2] + sgt[k][nd * 2 + 1]) % MOD;
}
void build(int nd, int le, int ri) {
  lzy[nd] = -1;
  if (le == ri) {
    for (int k = 0; k <= 5; ++k)
      sgt[k][nd] = 1LL * (psm[k][le] - psm[k][le - 1] + MOD) * arr[le] % MOD;
  } else {
    int md = (le + ri) / 2;
    build(nd * 2, le, md);
    build(nd * 2 + 1, md + 1, ri);
    updateNode(nd, le, ri);
  }
}
void update(int nd, int le, int ri, int st, int en, int vl) {
  updateLazy(nd, le, ri);
  if (en < le or ri < st) return;
  if (st <= le and ri <= en) {
    lzy[nd] = vl;
    updateLazy(nd, le, ri);
  } else {
    int md = (le + ri) / 2;
    update(nd * 2, le, md, st, en, vl);
    update(nd * 2 + 1, md + 1, ri, st, en, vl);
    updateNode(nd, le, ri);
  }
}
int v[6];
void query(int nd, int le, int ri, int st, int en) {
  updateLazy(nd, le, ri);
  if (en < le or ri < st) return;
  if (st <= le and ri <= en) {
    for (int k = 0; k <= 5; ++k) v[k] = (v[k] + sgt[k][nd]) % MOD;
  } else {
    int md = (le + ri) / 2;
    query(nd * 2, le, md, st, en);
    query(nd * 2 + 1, md + 1, ri, st, en);
  }
}
int main(void) {
  int n, q;
  cin >> n >> q;
  for (int i = 1; i <= n; ++i) cin >> arr[i];
  for (int k = 0; k <= 5; ++k)
    for (int i = 1; i <= n; ++i) psm[k][i] = (pwr(i, k) + psm[k][i - 1]) % MOD;
  build(1, 1, n);
  while (q--) {
    char ch;
    int l, r, x;
    cin >> ch >> l >> r >> x;
    if (ch == '=')
      update(1, 1, n, l, r, x);
    else {
      for (int k = 0; k <= 5; ++k) v[k] = 0;
      query(1, 1, n, l, r);
      int ans = 0;
      for (int k = 0; k <= x; ++k)
        ans = (1LL * coef[x][k] * v[k] % MOD * pwr(1 - l, x - k) + ans) % MOD;
      cout << (ans % MOD + MOD) % MOD << "\n";
    }
  }
  return 0;
}