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 = 100005;
const long long mod = (int)1e9 + 7;
long long seg[N << 2][6], n, sum[N][6], chg[N << 2];
unsigned long long C[6][6];
inline long long shift2(int pos, int k, int v) {
  long long ans = seg[pos][k];
  long long t = v;
  for (int i = k - 1; i >= 0; i--) {
    ans = (ans + C[k][i] * t * seg[pos][i]) % mod;
    t = (t * v % mod);
  }
  return ans;
}
inline long long shift(int rt, int k, int v) {
  long long ans = seg[rt][k], t = v;
  for (int i = k - 1; i >= 0; i--) {
    ans = (ans + (t * C[k][i] % mod) * seg[rt][i]) % mod;
    t = (t * v) % mod;
  }
  return ans;
}
void init() {
  int i, j;
  C[0][0] = 1;
  for (i = 1; i <= 5; i++) {
    C[i][0] = 1;
    for (j = 0; j <= i; j++) C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
  }
  for (i = 1; i <= n; i++) {
    long long v = 1;
    for (j = 0; j <= 5; j++) {
      sum[i][j] = (sum[i - 1][j] + v) % mod;
      v = (v * i) % mod;
    }
  }
  memset(chg, -1, sizeof(chg));
}
inline void upt(int pos, int l, int r, int val) {
  for (int i = 0; i < 6; i++) seg[pos][i] = 1LL * val * sum[r - l + 1][i] % mod;
}
inline void down(int v, int l, int r, int rt) {
  for (int i = 0; i <= 5; i++) seg[rt][i] = (v * sum[r - l + 1][i]) % mod;
}
inline void pushdown(int l, int r, int rt) {
  int m = (l + r) >> 1;
  int lc = rt << 1;
  int rc = lc | 1;
  if (chg[rt] != -1) {
    chg[rt << 1] = chg[rt << 1 | 1] = chg[rt];
    down(chg[rt], l, m, lc);
    down(chg[rt], m + 1, r, rc);
    chg[rt] = -1;
  }
}
inline void pushup(int l, int r, int rt) {
  int m = (l + r) >> 1;
  for (int i = 0; i <= 5; i++)
    seg[rt][i] = (seg[rt << 1][i] + shift(rt << 1 | 1, i, m - l + 1)) % mod;
}
void update(int L, int R, int v, int l = 1, int r = n, int rt = 1) {
  if (L <= l && r <= R) {
    down(v, l, r, rt);
    chg[rt] = v;
    return;
  }
  int m = (l + r) >> 1;
  pushdown(l, r, rt);
  if (L <= m) update(L, R, v, l, m, rt << 1);
  if (R > m) update(L, R, v, m + 1, r, rt << 1 | 1);
  pushup(l, r, rt);
}
long long ans;
int now;
void query(int L, int R, int k, int l = 1, int r = n, int rt = 1) {
  if (L <= l && r <= R) {
    ans = (ans + shift(rt, k, now)) % mod;
    now += r - l + 1;
    return;
  }
  int m = (l + r) >> 1;
  pushdown(l, r, rt);
  if (L <= m) query(L, R, k, l, m, rt << 1);
  if (R > m) query(L, R, k, m + 1, r, rt << 1 | 1);
  pushup(l, r, rt);
}
int main() {
  int m;
  cin >> n >> m;
  init();
  for (int i = 1; i <= n; i++) {
    int val;
    scanf("%d", &val);
    update(i, i, val);
  }
  char cmd[4];
  while (m--) {
    int l, r, k;
    scanf("%s%d%d%d", cmd, &l, &r, &k);
    if (cmd[0] == '=')
      update(l, r, k);
    else {
      ans = now = 0;
      query(l, r, k);
      printf("%I64d\n", ans);
    }
  }
}