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 long long mod = 1e9 + 7;
long long mul(long long a, long long b) {
  a %= mod;
  b %= mod;
  return (a * b) % mod;
}
struct vertex {
  long long S[6];

 public:
  vertex() {
    S[0] = 1;
    fill(S + 1, S + 6, 0);
  }
  vertex(long long p, long long v) {
    S[0] = v % mod;
    for (int i = 0; i < (5); i++) S[i + 1] = mul(S[i], p + 1);
  }
  vertex operator+(const vertex& o) {
    vertex ret;
    for (int i = 0; i < (6); i++) ret.S[i] = (S[i] + o.S[i]) % mod;
    return ret;
  }
};
ostream& operator<<(ostream& st, const vertex& v) {
  st << "(";
  for (int i = 0; i < (6); i++) {
    if (i) st << " ,";
    st << v.S[i];
  }
  st << " )";
  return st;
}
const int MAX = 1e5 + 1e3;
vertex ST[MAX << 2];
long long A[MAX], LAZY[MAX << 2], C[6][6];
int n, m;
long long SUMPOW[6][MAX];
vertex build(int node, int s, int e) {
  LAZY[node] = -1;
  if (s == e) return ST[node] = vertex(s + 0LL, A[s]);
  int m = (s + e) >> 1, left = node << 1, right = left | 1;
  return ST[node] = build(left, s, m) + build(right, m + 1, e);
}
void update(int node, int s, int e, long long v) {
  v %= mod;
  LAZY[node] = v;
  for (int i = 0; i < (6); i++) {
    long long tmp = SUMPOW[i][e] - SUMPOW[i][s - 1];
    if (tmp < 0) tmp += mod;
    ST[node].S[i] = mul(v, tmp);
  }
}
void forward(int node, int s, int e) {
  if (LAZY[node] == -1) return;
  int m = (s + e) >> 1, left = node << 1, right = left | 1;
  update(left, s, m, LAZY[node]);
  update(right, m + 1, e, LAZY[node]);
  LAZY[node] = -1;
}
void update(int node, int s, int e, int l, int r, long long v) {
  if (l <= s && e <= r) return update(node, s, e, v);
  forward(node, s, e);
  int m = (s + e) >> 1, left = node << 1, right = left | 1;
  if (r <= m)
    update(left, s, m, l, r, v);
  else if (m < l)
    update(right, m + 1, e, l, r, v);
  else
    update(left, s, m, l, m, v), update(right, m + 1, e, m + 1, r, v);
  ST[node] = ST[left] + ST[right];
}
vertex query(int node, int s, int e, int l, int r) {
  if (l <= s && e <= r) return ST[node];
  forward(node, s, e);
  int m = (s + e) >> 1, left = node << 1, right = left | 1;
  if (r <= m)
    return query(left, s, m, l, r);
  else if (m < l)
    return query(right, m + 1, e, l, r);
  else
    return query(left, s, m, l, m) + query(right, m + 1, e, m + 1, r);
}
void init() {
  scanf("%d %d", &n, &m);
  for (int i = 0; i < (n); i++) scanf("%I64d", A + i + 1);
  build(1, 1, n);
  for (int i = 0; i < (n + 1); i++) {
    long long j = 1;
    for (int p = 0; p < (6); p++) {
      SUMPOW[p][i] = j;
      if (i) {
        SUMPOW[p][i] += SUMPOW[p][i - 1];
        if (SUMPOW[p][i] >= mod) SUMPOW[p][i] -= mod;
      }
      j *= i + 1;
      j %= mod;
    }
  }
  for (int i = 0; i < (6); i++) {
    C[i][0] = 1;
    for (int j = (1); j <= (i); j++) C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
  }
}
int main() {
  init();
  char s[3];
  int l, r, x;
  while (m--) {
    scanf("%s %d %d %d", s, &l, &r, &x);
    if (s[0] == '=')
      update(1, 1, n, l, r, x);
    else {
      vertex Q = query(1, 1, n, l, r);
      long long ans = 0, q = 1;
      for (int i = 0; i < (x + 1); i++) {
        ans += mul(C[x][i], mul(q, Q.S[x - i]));
        ans %= mod;
        q *= -l;
        q %= mod;
        if (q < 0) q += mod;
      }
      printf("%I64d\n", ans);
    }
  }
  return 0;
}