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 maxn = 1e5 + 10, maxk = 6, mod = 1e9 + 7;
int add(int a, int b) { return (a += b) >= mod ? a - mod : a; }
int sub(int a, int b) { return (a -= b) < 0 ? a + mod : a; }
int mul(int a, int b) { return a * 1ll * b % mod; }
int kpw[maxk][maxn], comb[maxk][maxn];
int fpow(int a, int n) {
  int ret = 1;
  for (; n; n >>= 1, a = mul(a, a))
    if (n & 1) ret = mul(ret, a);
  return ret;
}
void init() {
  for (int i = 0; i < maxk; ++i) {
    for (int j = 1; j < maxn; ++j) kpw[i][j] = add(kpw[i][j - 1], fpow(j, i));
  }
  comb[0][0] = 1;
  for (int i = 1; i < maxk; ++i) {
    for (int j = 0; j < maxn; ++j) {
      comb[i][j] = comb[i - 1][j];
      if (j > 0) comb[i][j] = add(comb[i][j], comb[i - 1][j - 1]);
    }
  }
}
int a[maxn];
struct segtree {
  struct data {
    int s[maxk];
    data() { memset(s, 0, sizeof(s)); }
    data(int a, int p) {
      for (int i = 0; i < maxk; ++i) {
        int pw = fpow(p, i);
        s[i] = mul(a, pw);
      }
    }
    data(int a, int l, int r) {
      for (int i = 0; i < maxk; ++i)
        s[i] = mul(a, sub(kpw[i][r], kpw[i][l - 1]));
    }
    data operator+(const data &rhs) const {
      data ret;
      for (int i = 0; i < maxk; ++i) ret.s[i] = add(s[i], rhs.s[i]);
      return ret;
    }
  };
  segtree *lc, *rc;
  data dat;
  int tag;
  segtree(int l, int r) {
    tag = -1;
    if (l == r)
      lc = rc = nullptr, dat = data(a[l], l);
    else
      lc = new segtree(l, ((l + r) >> 1)),
      rc = new segtree(((l + r) >> 1) + 1, r), pull();
  }
  void pull() { dat = lc->dat + rc->dat; }
  void modify(int l, int r, int ql, int qr, int x) {
    push(l, r);
    if (l > qr || ql > r) return;
    if (l >= ql && r <= qr) return tag = x, dat = data(x, l, r), void();
    lc->modify(l, ((l + r) >> 1), ql, qr, x);
    rc->modify(((l + r) >> 1) + 1, r, ql, qr, x);
    pull();
  }
  data query(int l, int r, int ql, int qr) {
    push(l, r);
    if (l > qr || ql > r) return data();
    if (l >= ql && r <= qr) return dat;
    return lc->query(l, ((l + r) >> 1), ql, qr) +
           rc->query(((l + r) >> 1) + 1, r, ql, qr);
  }
  void push(int l, int r) {
    if (l == r || tag == -1) return;
    lc->tag = tag;
    lc->dat = data(tag, l, ((l + r) >> 1));
    rc->tag = tag;
    rc->dat = data(tag, ((l + r) >> 1) + 1, r);
    tag = -1;
  }
} * sgt;
int main() {
  init();
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  sgt = new segtree(1, n);
  while (m--) {
    char c;
    int l, r, k;
    cin >> c >> l >> r >> k;
    if (c == '=') {
      sgt->modify(1, n, l, r, k);
      continue;
    }
    segtree::data dat = sgt->query(1, n, l, r);
    int ans = 0, coef = 1;
    for (int i = 0; i <= k; ++i) {
      int t = mul(comb[k][i], dat.s[k - i]);
      t = mul(t, fpow(l - 1, i));
      if (coef == 1)
        ans = add(ans, t);
      else
        ans = sub(ans, t);
      coef = -coef;
    }
    cout << ans << endl;
  }
  return 0;
}