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;
inline int getint() {
  static char c;
  while ((c = getchar()) < '0' || c > '9')
    ;
  int res = c - '0';
  while ((c = getchar()) >= '0' && c <= '9') res = res * 10 + c - '0';
  return res;
}
const int M = 1000000007;
const int MaxN = 100005;
const int MaxSegN = MaxN * 3;
const int MaxNK = 6;
int n, q;
int c[MaxNK][MaxNK];
int pwl[MaxN][MaxNK];
int pwd[MaxN][MaxNK];
int sum[MaxN][MaxNK];
inline void initMath() {
  for (int i = 0; i < MaxNK; ++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 = 1; i <= n; ++i) {
    pwl[i][0] = pwd[i][0] = 1;
    sum[i][0] = i;
  }
  for (int k = 1; k < MaxNK; ++k) {
    for (int i = 1; i <= n; ++i) {
      pwd[i][k] = (long long)pwd[i][k - 1] * i % M;
      pwl[i][k] = ((long long)pwl[i][k - 1] * (1 - i) % M + M) % M;
      sum[i][k] = (sum[i - 1][k] + pwd[i][k]) % M;
    }
  }
}
struct seg_node {
  int cov;
  int sum[MaxNK];
};
seg_node seg[MaxSegN];
inline void seg_update(const int &p) {
  int l = p << 1 | 0, r = p << 1 | 1;
  for (int k = 0; k < MaxNK; ++k)
    seg[p].sum[k] = (seg[l].sum[k] + seg[r].sum[k]) % M;
}
inline void seg_tag_cov(const int &p, const int &pL, const int &pR,
                        const int &w) {
  seg[p].cov = w;
  for (int k = 0; k < MaxNK; ++k) {
    int t = ((sum[pR][k] - sum[pL - 1][k]) % M + M) % M;
    seg[p].sum[k] = (long long)t * w % M;
  }
}
inline void seg_tag_down(const int &p, const int &pL, const int &pR) {
  if (seg[p].cov != -1) {
    int pM = pL + pR >> 1;
    seg_tag_cov(p << 1 | 0, pL, pM, seg[p].cov);
    seg_tag_cov(p << 1 | 1, pM + 1, pR, seg[p].cov);
    seg[p].cov = -1;
  }
}
void seg_build(const int &p, const int &pL, const int &pR) {
  seg[p].cov = -1;
  if (pL == pR) {
    int w = getint();
    for (int k = 0; k < MaxNK; ++k)
      seg[p].sum[k] = (long long)w * pwd[pL][k] % M;
    return;
  }
  int pM = pL + pR >> 1;
  seg_build(p << 1 | 0, pL, pM);
  seg_build(p << 1 | 1, pM + 1, pR);
  seg_update(p);
}
void seg_cover(const int &p, const int &pL, const int &pR, const int &qL,
               const int &qR, const int &w) {
  if (qL <= pL && qR >= pR) {
    seg_tag_cov(p, pL, pR, w);
    return;
  }
  seg_tag_down(p, pL, pR);
  int pM = pL + pR >> 1;
  if (qL <= pM) seg_cover(p << 1 | 0, pL, pM, qL, qR, w);
  if (qR > pM) seg_cover(p << 1 | 1, pM + 1, pR, qL, qR, w);
  seg_update(p);
}
int seg_query(const int &p, const int &pL, const int &pR, const int &qL,
              const int &qR, const int &k) {
  if (qL <= pL && qR >= pR) return seg[p].sum[k];
  seg_tag_down(p, pL, pR);
  int pM = pL + pR >> 1;
  int res = 0;
  if (qL <= pM) {
    int w = seg_query(p << 1 | 0, pL, pM, qL, qR, k);
    res = (res + w) % M;
  }
  if (qR > pM) {
    int w = seg_query(p << 1 | 1, pM + 1, pR, qL, qR, k);
    res = (res + w) % M;
  }
  return res;
}
int main() {
  cin >> n >> q;
  initMath();
  seg_build(1, 1, n);
  while (q--) {
    char type;
    while ((type = getchar()) != '=' && type != '?')
      ;
    if (type == '=') {
      int l = getint(), r = getint(), w = getint();
      seg_cover(1, 1, n, l, r, w);
    } else {
      int l = getint(), r = getint(), k = getint();
      int ans = 0;
      for (int i = 0; i <= k; ++i) {
        int w = seg_query(1, 1, n, l, r, i);
        ans = ((ans + (long long)w * c[k][i] % M * pwl[l][k - i] % M) % M + M) %
              M;
      }
      printf("%d\n", ans);
    }
  }
  return 0;
}