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 N = 100010, mod = 1000000007;
int n, m;
int t[N * 4][6], lazy[N * 4];
int power[6][N], a[N];
int C[6][6];
struct Node {
  int d[6];
};
signed mo(int x, int y) { return x + y >= mod ? x + y - mod : x + y; }
void init() {
  C[0][0] = 1;
  for (int i = 1; i < 6; i++) {
    C[i][0] = C[i][i] = 1;
    for (int j = 1; j < i; j++) {
      C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
    }
  }
  for (int i = 0; i < N; i++) power[0][i] = 1;
  for (int j = 1; j < 6; j++) {
    for (int i = 1; i < N; i++) {
      power[j][i] = 1ll * power[j - 1][i] * i % mod;
    }
  }
  for (int j = 0; j < 6; j++) {
    for (int i = 1; i < N; i++) {
      power[j][i] = mo(power[j][i], power[j][i - 1]);
    }
  }
}
int get(int q, int l, int r) { return mo(power[q][r], mod - power[q][l - 1]); }
void pushup(int q) {
  for (int i = 0; i < 6; i++) {
    t[q][i] = mo(t[q << 1][i], t[q << 1 | 1][i]);
  }
}
void pushdown(int q, int l, int mid, int r) {
  if (~lazy[q]) {
    lazy[q << 1] = lazy[q << 1 | 1] = lazy[q];
    for (int j = 0; j < 6; j++) {
      t[q << 1][j] = 1ll * lazy[q] * get(j, l, mid) % mod;
      t[q << 1 | 1][j] = 1ll * lazy[q] * get(j, mid + 1, r) % mod;
    }
    lazy[q] = -1;
  }
}
void build(int q, int l, int r) {
  lazy[q] = -1;
  if (l == r) {
    for (int j = 0; j < 6; j++) {
      t[q][j] = 1ll * a[l] * get(j, l, l) % mod;
    }
    return;
  }
  int mid = (l + r) >> 1;
  build(q << 1, l, mid);
  build(q << 1 | 1, mid + 1, r);
  pushup(q);
}
void update(int q, int l, int r, int L, int R, int x) {
  if (L == l && R == r) {
    lazy[q] = x;
    for (int i = 0; i < 6; i++) {
      t[q][i] = 1ll * x * get(i, l, r) % mod;
    }
    return;
  }
  int mid = (l + r) >> 1;
  pushdown(q, l, mid, r);
  if (R <= mid)
    update(q << 1, l, mid, L, R, x);
  else if (L > mid)
    update(q << 1 | 1, mid + 1, r, L, R, x);
  else {
    update(q << 1, l, mid, L, mid, x);
    update(q << 1 | 1, mid + 1, r, mid + 1, R, x);
  }
  pushup(q);
}
Node query(int q, int l, int r, int L, int R) {
  Node res;
  if (l == L && r == R) {
    for (int i = 0; i < 6; i++) {
      res.d[i] = t[q][i];
    }
    return res;
  }
  Node resl, resr;
  int mid = (l + r) >> 1;
  pushdown(q, l, mid, r);
  for (int j = 0; j < 6; j++) resl.d[j] = resr.d[j] = 0;
  if (R <= mid)
    resl = query(q << 1, l, mid, L, R);
  else if (L > mid)
    resr = query(q << 1 | 1, mid + 1, r, L, R);
  else {
    resl = query(q << 1, l, mid, L, mid);
    resr = query(q << 1 | 1, mid + 1, r, mid + 1, R);
  }
  for (int i = 0; i < 6; i++) {
    resl.d[i] = mo(resl.d[i], resr.d[i]);
  }
  return resl;
}
int main() {
  init();
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  build(1, 1, n);
  while (m--) {
    char c;
    while (scanf("%c", &c), c != '?' && c != '=')
      ;
    if (c == '=') {
      int l, r, x;
      scanf("%d%d%d", &l, &r, &x);
      update(1, 1, n, l, r, x);
    } else {
      int l, r, k;
      scanf("%d%d%d", &l, &r, &k);
      Node u = query(1, 1, n, l, r);
      int res, ans = 0;
      for (int j = 0; j <= k; j++) {
        if (l > 1)
          res = get(k - j, l - 1, l - 1);
        else
          res = power[k - j][l - 1];
        if (((k ^ j) & 1) && res) res = mod - res;
        ans = mo(ans, 1ll * res * C[k][j] % mod * u.d[j] % mod);
      }
      printf("%d\n", ans);
    }
  }
}