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;
int n;
int ans[6];
int seg[300000][6], tag[300000];
void pu(int rt) {
  for (int i = 0; i <= 5; i++) {
    seg[rt][i] = seg[rt << 1][i] + seg[rt << 1 | 1][i];
    if (seg[rt][i] >= 1000000007) seg[rt][i] -= 1000000007;
  }
}
void build(int l, int r, int rt) {
  tag[rt] = -1;
  if (l == r) {
    int x;
    scanf("%d", &x);
    seg[rt][0] = x;
    for (int i = 1; i <= 5; i++)
      seg[rt][i] = 1ll * seg[rt][i - 1] * l % 1000000007;
  } else {
    int mid = l + r >> 1;
    build(l, mid, rt << 1);
    build(mid + 1, r, rt << 1 | 1);
    pu(rt);
  }
}
int qp(int a, int b) {
  int ans = 1;
  do {
    if (b & 1) ans = 1ll * ans * a % 1000000007;
    a = 1ll * a * a % 1000000007;
  } while (b >>= 1);
  return ans;
}
int ss;
int su(int n, int k) {
  if (k == 0) return n;
  if (k == 1) return 1ll * n * (n + 1) / 2 % 1000000007;
  if (k == 2) return 1ll * n * (n + 1) * (2 * n + 1) / 6 % 1000000007;
  if (k == 3) {
    int t = 1ll * n * (n + 1) / 2 % 1000000007;
    return 1ll * t * t % 1000000007;
  }
  if (k == 4)
    return (1ll * n * (n + 1) * (2 * n + 1) % 1000000007) *
           ((3ll * n * n + 3 * n - 1) % 1000000007) % 1000000007 * 233333335 %
           1000000007;
  if (k == 5)
    return 1ll * (n * (n + 1ll) % 1000000007) * (n * (n + 1ll) % 1000000007) %
           1000000007 * (2ll * n * n % 1000000007 + 2 * n - 1) % 1000000007 *
           83333334 % 1000000007;
}
int l1, r1, v;
void cov(int rt, int x, int l, int r) {
  tag[rt] = x;
  for (int i = 0; i <= 5; i++) {
    seg[rt][i] = su(r, i) - su(l - 1, i);
    if (seg[rt][i] < 0) seg[rt][i] += 1000000007;
    seg[rt][i] = 1ll * seg[rt][i] * x % 1000000007;
  }
}
void pd(int rt, int l, int r) {
  if (~tag[rt]) {
    cov(rt << 1, tag[rt], l, l + r >> 1);
    cov(rt << 1 | 1, tag[rt], (l + r >> 1) + 1, r);
    tag[rt] = -1;
  }
}
void que(int l, int r, int rt) {
  if (l1 <= l && r <= r1) {
    for (int i = 0; i <= 5; i++) {
      ans[i] += seg[rt][i];
      if (ans[i] >= 1000000007) ans[i] -= 1000000007;
    }
  } else {
    pd(rt, l, r);
    int mid = l + r >> 1;
    if (l1 <= mid) que(l, mid, rt << 1);
    if (r1 > mid) que(mid + 1, r, rt << 1 | 1);
  }
}
void upd(int l, int r, int rt) {
  if (l1 <= l && r <= r1) {
    cov(rt, v, l, r);
  } else {
    pd(rt, l, r);
    int mid = l + r >> 1;
    if (l1 <= mid) upd(l, mid, rt << 1);
    if (r1 > mid) upd(mid + 1, r, rt << 1 | 1);
    pu(rt);
  }
}
int c[6][6];
int main() {
  c[0][0] = 1;
  for (int i = 1; i <= 5; i++) {
    c[i][0] = 1;
    for (int j = 1; j <= i; j++) c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
  }
  ss = qp(30, 1000000007 - 2);
  int q;
  scanf("%d%d", &n, &q);
  build(1, n, 1);
  while (q--) {
    char c;
    while ((c = getchar()) != '=' && c != '?')
      ;
    int t;
    scanf("%d%d%d", &l1, &r1, &t);
    if (c == '=') {
      v = t;
      upd(1, n, 1);
    } else {
      memset(ans, 0, sizeof(ans));
      que(1, n, 1);
      int su = 0;
      for (int j = 0, sg = 1; j <= t; j++) {
        su = (su + 1ll * ans[t - j] * sg % 1000000007 * ::c[t][j]) % 1000000007;
        sg = 1ll * sg * (1 - l1) % 1000000007;
      }
      su = (su + 1000000007) % 1000000007;
      printf("%d\n", su);
    }
  }
  return 0;
}