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 = 1e5 + 7;
const int M = 6;
const int inf = 1e9 + 7;
const long long base = 1e18;
const double pi = acos(-1);
const double ep = 1e-9;
long long pw(long long x, int k) {
  if (k == 0) return 1;
  long long tmp = pw(x, k / 2);
  tmp = tmp * tmp % inf;
  if (k & 1) tmp = tmp * x % inf;
  if (tmp < 0) tmp += inf;
  return tmp;
}
int C[M][M];
long long L[N][M];
int n, m;
void init() {
  C[0][0] = 1;
  for (int i = (int)1; i < (int)M; i++) {
    C[i][0] = C[i][i] = 1;
    for (int j = (int)1; j < (int)i; j++)
      C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
  }
  for (int i = (int)1; i < (int)N; i++) {
    for (int j = (int)0; j < (int)M; j++) {
      L[i][j] = (L[i - 1][j] + pw(i, j)) % inf;
    }
  }
}
class SegmentTree {
 public:
  long long a[N * 4];
  bool b[N * 4];
  long long sum[N * 4];
  int k;
  void up(int i, int l, int r, int val) {
    a[i] = val;
    sum[i] = a[i] * (L[r][k] - L[l - 1][k] + inf) % inf;
    b[i] = true;
  }
  void update(int i, int l, int r, int u, int v, int val) {
    int g = (l + r) >> 1, next = i << 1;
    if (b[i]) {
      if (l < r) {
        up(next, l, g, a[i]);
        up(next + 1, g + 1, r, a[i]);
      }
      b[i] = 0;
    }
    if (l == u && r == v) {
      up(i, l, r, val);
      return;
    }
    if (u <= g) update(next, l, g, u, min(g, v), val);
    if (g < v) update(next + 1, g + 1, r, max(g + 1, u), v, val);
    sum[i] = sum[next] + sum[next + 1];
    b[i] = 0;
    a[i] = 0;
  }
  long long kq;
  void get(int i, int l, int r, int u, int v) {
    int g = (l + r) >> 1, next = i << 1;
    if (b[i]) {
      if (l < r) {
        up(next, l, g, a[i]);
        up(next + 1, g + 1, r, a[i]);
      }
      b[i] = 0;
    }
    if (l == u && r == v) {
      kq = (kq + sum[i]) % inf;
      return;
    }
    if (u <= g) get(next, l, g, u, min(g, v));
    if (g < v) get(next + 1, g + 1, r, max(u, g + 1), v);
    sum[i] = sum[next] + sum[next + 1];
    b[i] = a[i] = 0;
  }
  long long get(int l, int r) {
    kq = 0;
    get(1, 1, n, l, r);
    return kq;
  }
};
SegmentTree tree[M];
int main() {
  init();
  cin >> n >> m;
  for (int j = (int)0; j < (int)M; j++) tree[j].k = j;
  for (int i = (int)1; i < (int)n + 1; i++) {
    int u;
    scanf("%d", &u);
    for (int j = (int)0; j < (int)M; j++) tree[j].update(1, 1, n, i, i, u);
  }
  while (m-- > 0) {
    char c;
    int u, v, k;
    for (c = getchar(); c != '?' && c != '='; c = getchar())
      ;
    scanf("%d%d%d", &u, &v, &k);
    if (c == '=') {
      for (int j = (int)0; j < (int)M; j++) tree[j].update(1, 1, n, u, v, k);
    } else {
      long long ans = 0;
      for (int j = (int)0; j < (int)k + 1; j++) {
        long long tmp = tree[j].get(u, v);
        ans = (ans + tmp * C[k][j] % inf * pw(-u + 1, k - j) % inf) % inf;
      }
      cout << ans << endl;
    }
  }
}