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 long long mod = 1000000007;
const long long inv2 = 500000004;
const long long inv6 = 166666668;
const long long inv4 = 250000002;
const long long inv30 = 233333335;
const long long inv12 = 83333334;
const int KKK = 5;
long long ipow(long long b, int e) {
  b = b % mod;
  long long r = 1;
  while (e-- > 0) r = (r * b) % mod;
  return r;
}
struct node {
  node *lc, *rc;
  size_t l, r;
  long long v;
  int k;
  bool flazy;
  long long lazy;
};
const int max_n = 100100;
const int max_t = 13 * max_n;
int tn;
node T[max_t], *troot[KKK + 1];
int n, m, a[max_n];
long long C[KKK + 1][KKK + 1];
long long P[max_n][KKK + 1];
long long Q[max_n][KKK + 1];
void lazy(node *x) {
  if (x->flazy) {
    x->v = (((x->lazy) * ((Q[x->r][x->k] - Q[x->l - 1][x->k] + mod))) % mod);
    x->flazy = false;
    if (x->l < x->r) {
      x->lc->flazy = true;
      x->rc->flazy = true;
      x->lc->lazy = x->lazy;
      x->rc->lazy = x->lazy;
    }
  }
}
long long query(node *x, size_t ql, size_t qr) {
  lazy(x);
  if (ql <= x->l && x->r <= qr)
    return x->v;
  else {
    long long ans = 0;
    if (ql <= x->lc->r) ans += query(x->lc, ql, qr);
    if (qr >= x->rc->l) ans += query(x->rc, ql, qr);
    return ans < mod ? ans : ans % mod;
  }
}
void modify(node *x, size_t ql, size_t qr, long long v) {
  lazy(x);
  if (ql <= x->l && x->r <= qr) {
    x->flazy = true;
    x->lazy = v;
    lazy(x);
  } else {
    if (ql <= x->lc->r) modify(x->lc, ql, qr, v);
    if (qr >= x->rc->l) modify(x->rc, ql, qr, v);
    lazy(x->lc);
    lazy(x->rc);
    x->v = x->lc->v + x->rc->v;
    x->v = x->v < mod ? x->v : x->v % mod;
  }
}
void build(node *x) {
  if (x->l == x->r) x->v = (((a[x->l]) * (P[x->l][x->k])) % mod);
  if (x->l < x->r) {
    int mid = (x->l + x->r) / 2;
    x->lc = &T[tn++];
    x->lc->l = x->l;
    x->lc->r = mid;
    x->lc->k = x->k;
    build(x->lc);
    x->rc = &T[tn++];
    x->rc->l = mid + 1;
    x->rc->r = x->r;
    x->rc->k = x->k;
    build(x->rc);
    x->v = x->lc->v + x->rc->v;
    x->v = x->v < mod ? x->v : x->v % mod;
  }
}
int op_query(int l, int r, int k) {
  long long ans = 0;
  for (int i = 0; i <= k; ++i)
    ans = (ans +
           ((((((C[k][i]) *
                (((((k - i) & 1 ? mod - 1 : 1) * (P[l - 1][k - i])) % mod))) %
               mod)) *
             (query(troot[i], l, r))) %
            mod)) %
          mod;
  return ans % mod;
}
long long iin() {
  char c = 0;
  long long u = 0;
  int b = 1;
  while (c < '0' || c > '9') {
    c = getchar();
    if (c == '-') b = -1;
  }
  while (c >= '0' && c <= '9') {
    u = u * 10 + c - '0';
    c = getchar();
  }
  return u;
}
int main() {
  for (int k = 0; k <= KKK; ++k) C[k][0] = 1;
  for (int k = 1; k <= KKK; ++k)
    for (int i = 1; i <= k; ++i)
      C[k][i] = (C[k - 1][i] + C[k - 1][i - 1]) % mod;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  for (int i = 0; i <= n; ++i)
    for (int k = 0; k <= KKK; ++k) P[i][k] = ipow(i, k);
  for (int k = 0; k <= KKK; ++k)
    for (int i = 0, z = 0; i <= n; ++i, z = (z + P[i][k]) % mod) Q[i][k] = z;
  for (int i = 0; i <= KKK; ++i) {
    troot[i] = &T[tn++];
    troot[i]->k = i;
    troot[i]->l = 1;
    troot[i]->r = n;
    build(troot[i]);
  }
  for (int i = 0; i < m; ++i) {
    char op[10];
    scanf("%s", op);
    if (op[0] == '?') {
      int l, r, k;
      scanf("%d%d%d", &l, &r, &k);
      int ans = op_query(l, r, k);
      printf("%d\n", ans);
    }
    if (op[0] == '=') {
      int l, r, x;
      scanf("%d%d%d", &l, &r, &x);
      for (int k = 0; k <= KKK; ++k) modify(troot[k], l, r, x);
    }
  }
  return 0;
}