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;
long long s[111111][6], a[111111][6];
struct Seg {
  int l, r;
  long long sum[6], sign;
} seg[111111 * 4];
void buildtree(int lf, int rg, int now);
void update(int lf, int rg, long long x, int nw);
void getnew(long long x, int nw);
long long query(int lf, int rg, int k, int nw);
int main() {
  int n, m;
  cin >> n >> m;
  for (long long i = 1; i <= n; i++) {
    long long k = 1;
    for (int j = 0; j < 6; j++) {
      s[i][j] = (s[i - 1][j] + k) % 1000000007ll;
      k = (k * i) % 1000000007ll;
    }
  }
  for (long long i = 1; i <= n; i++) {
    cin >> a[i][0];
    for (int j = 1; j < 6; j++) a[i][j] = (a[i][j - 1] * i) % 1000000007ll;
  }
  buildtree(1, n, 1);
  for (int i = 0; i < m; i++) {
    char c;
    cin >> c;
    if (c == '=') {
      int l, r;
      cin >> l >> r;
      long long x;
      cin >> x;
      update(l, r, x, 1);
    } else {
      int l, r, k;
      cin >> l >> r >> k;
      long long l1[6];
      l1[0] = 1;
      l1[1] = l - 1;
      for (int j = 2; j < 6; j++) l1[j] = (l1[j - 1] * l1[1]) % 1000000007ll;
      long long ans = query(l, r, k, 1);
      if (k == 1) {
        ans -= (l1[1] * query(l, r, 0, 1)) % 1000000007ll;
        ans = (ans + 1000000007ll) % 1000000007ll;
      } else if (k == 2) {
        ans += (l1[2] * query(l, r, 0, 1)) % 1000000007ll;
        ans = (ans + 1000000007ll) % 1000000007ll;
        ans -=
            (((2 * l1[1]) % 1000000007ll) * query(l, r, 1, 1)) % 1000000007ll;
        ans = (ans + 1000000007ll) % 1000000007ll;
      } else if (k == 3) {
        ans -= (l1[3] * query(l, r, 0, 1)) % 1000000007ll;
        ans = (ans + 1000000007ll) % 1000000007ll;
        ans +=
            (((3 * l1[2]) % 1000000007ll) * query(l, r, 1, 1)) % 1000000007ll;
        ans = (ans + 1000000007ll) % 1000000007ll;
        ans -=
            (((3 * l1[1]) % 1000000007ll) * query(l, r, 2, 1)) % 1000000007ll;
        ans = (ans + 1000000007ll) % 1000000007ll;
      } else if (k == 4) {
        ans += (l1[4] * query(l, r, 0, 1)) % 1000000007ll;
        ans = (ans + 1000000007ll) % 1000000007ll;
        ans -=
            (((4 * l1[3]) % 1000000007ll) * query(l, r, 1, 1)) % 1000000007ll;
        ans = (ans + 1000000007ll) % 1000000007ll;
        ans +=
            (((6 * l1[2]) % 1000000007ll) * query(l, r, 2, 1)) % 1000000007ll;
        ans = (ans + 1000000007ll) % 1000000007ll;
        ans -=
            (((4 * l1[1]) % 1000000007ll) * query(l, r, 3, 1)) % 1000000007ll;
        ans = (ans + 1000000007ll) % 1000000007ll;
      } else if (k == 5) {
        ans -= (l1[5] * query(l, r, 0, 1)) % 1000000007ll;
        ans = (ans + 1000000007ll) % 1000000007ll;
        ans +=
            (((5 * l1[4]) % 1000000007ll) * query(l, r, 1, 1)) % 1000000007ll;
        ans = (ans + 1000000007ll) % 1000000007ll;
        ans -=
            (((10 * l1[3]) % 1000000007ll) * query(l, r, 2, 1)) % 1000000007ll;
        ans = (ans + 1000000007ll) % 1000000007ll;
        ans +=
            (((10 * l1[2]) % 1000000007ll) * query(l, r, 3, 1)) % 1000000007ll;
        ans = (ans + 1000000007ll) % 1000000007ll;
        ans -=
            (((5 * l1[1]) % 1000000007ll) * query(l, r, 4, 1)) % 1000000007ll;
        ans = (ans + 1000000007ll) % 1000000007ll;
      }
      cout << ans << endl;
    }
  }
  return 0;
}
void buildtree(int lf, int rg, int now) {
  seg[now].l = lf;
  seg[now].r = rg;
  seg[now].sign = -1;
  if (lf == rg) {
    for (int i = 0; i < 6; i++) seg[now].sum[i] = a[lf][i];
    return;
  }
  int md = (lf + rg) / 2;
  buildtree(lf, md, now * 2);
  buildtree(md + 1, rg, now * 2 + 1);
  for (int i = 0; i < 6; i++)
    seg[now].sum[i] =
        (seg[now * 2].sum[i] + seg[now * 2 + 1].sum[i]) % 1000000007ll;
}
void update(int lf, int rg, long long x, int nw) {
  if (lf <= seg[nw].l && seg[nw].r <= rg) {
    getnew(x, nw);
    return;
  }
  if (seg[nw].sign != -1) {
    getnew(seg[nw].sign, nw * 2);
    getnew(seg[nw].sign, nw * 2 + 1);
    seg[nw].sign = -1;
  }
  int md = (seg[nw].l + seg[nw].r) / 2;
  if (lf <= md) update(lf, rg, x, nw * 2);
  if (rg > md) update(lf, rg, x, nw * 2 + 1);
  for (int i = 0; i < 6; i++)
    seg[nw].sum[i] =
        (seg[nw * 2].sum[i] + seg[nw * 2 + 1].sum[i]) % 1000000007ll;
}
void getnew(long long x, int nw) {
  seg[nw].sign = x;
  int l = seg[nw].l, r = seg[nw].r;
  for (int i = 0; i < 6; i++)
    seg[nw].sum[i] =
        (((s[r][i] - s[l - 1][i] + 1000000007ll) % 1000000007ll) * x) %
        1000000007ll;
}
long long query(int lf, int rg, int k, int nw) {
  if (lf <= seg[nw].l && seg[nw].r <= rg) return seg[nw].sum[k];
  if (seg[nw].sign != -1) {
    getnew(seg[nw].sign, nw * 2);
    getnew(seg[nw].sign, nw * 2 + 1);
    seg[nw].sign = -1;
  }
  long long ret = 0;
  int md = (seg[nw].l + seg[nw].r) / 2;
  if (lf <= md) ret += query(lf, rg, k, nw * 2);
  if (rg > md) ret += query(lf, rg, k, nw * 2 + 1);
  for (int i = 0; i < 6; i++)
    seg[nw].sum[i] =
        (seg[nw * 2].sum[i] + seg[nw * 2 + 1].sum[i]) % 1000000007ll;
  return ret % 1000000007ll;
}