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>
const int K = 6;
const int MAX = 100015;
const int oo = 1 << 30;
const long long MOD = (long long)1e9 + 7;
using namespace std;
int a[MAX];
long long tree[MAX << 2][6];
long long C[6][6];
long long lazy[MAX << 2];
long long cal[MAX][K];
long long power(long long a, int b) {
  if (a == 0) return 0;
  long long ans = 1;
  for (int i = 0; i < b; i++) ans = (ans * a) % MOD;
  return ans;
}
void nCk() {
  int i, j;
  for (i = 0; i < K; i++) C[i][i] = C[i][0] = 1;
  for (i = 1; i < K; i++)
    for (j = 1; j < i; j++) C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
}
void pre(int n, int l, int r, long long val) {
  for (int i = 0; i < K; i++) {
    tree[n][i] = (cal[r - l + 1][i] * val) % MOD;
  }
}
void init(int n, int l, int r) {
  int i, j, k;
  lazy[n] = -1;
  if (l == r) {
    for (i = 0; i < K; i++) tree[n][i] = a[l];
  } else {
    int m = (l + r) >> 1;
    long long LF = m - l + 1;
    init(((n)*2), l, m);
    init(((n)*2 + 1), m + 1, r);
    for (k = 0; k < K; k++) {
      tree[n][k] = (tree[((n)*2)][k] + tree[((n)*2 + 1)][k]) % MOD;
      for (j = 1; j <= k; j++) {
        tree[n][k] = (tree[n][k] + (((C[k][j] * power(LF, j)) % MOD) *
                                    tree[((n)*2 + 1)][k - j]) %
                                       MOD) %
                     MOD;
      }
    }
  }
}
void read(int n, int l, int r, int b, int e, int k, vector<long long> &ans) {
  if (lazy[n] != -1) {
    if (l != r) lazy[((n)*2)] = lazy[((n)*2 + 1)] = lazy[n];
    pre(n, l, r, lazy[n]);
    lazy[n] = -1;
  }
  if (b > r || e < l) return;
  if (l >= b && r <= e) {
    for (int i = 0; i <= k; i++) ans[i] = tree[n][i];
  } else {
    int m = (l + r) >> 1, j, i;
    vector<long long> rl(k + 1), rr(k + 1);
    read(((n)*2), l, m, b, e, k, rl);
    read(((n)*2 + 1), m + 1, r, b, e, k, rr);
    long long ll = max(m - max(l, b) + 1, 0);
    for (i = 0; i <= k; i++) {
      ans[i] = (rl[i] + rr[i]) % MOD;
      for (j = 1; j <= i; j++) {
        ans[i] =
            (ans[i] + ((C[i][j] * power(ll, j) % MOD) * rr[i - j]) % MOD) % MOD;
      }
    }
  }
}
void update(int n, int l, int r, int b, int e, int val) {
  if (lazy[n] != -1) {
    if (l != r) lazy[((n)*2)] = lazy[((n)*2 + 1)] = lazy[n];
    pre(n, l, r, lazy[n]);
    lazy[n] = -1;
  }
  if (b > r || e < l) return;
  if (b <= l && r <= e) {
    if (l != r) lazy[((n)*2)] = lazy[((n)*2 + 1)] = val;
    pre(n, l, r, val);
  } else {
    int m = (l + r) >> 1, j, k;
    long long LF = m - l + 1;
    update(((n)*2), l, m, b, e, val);
    update(((n)*2 + 1), m + 1, r, b, e, val);
    for (k = 0; k < K; k++) {
      tree[n][k] = (tree[((n)*2)][k] + tree[((n)*2 + 1)][k]) % MOD;
      for (j = 1; j <= k; j++) {
        tree[n][k] = (tree[n][k] + (((C[k][j] * power(LF, j)) % MOD) *
                                    tree[((n)*2 + 1)][k - j]) %
                                       MOD) %
                     MOD;
      }
    }
  }
}
int main() {
  int N, M, i, j, l, r, x;
  char t[5];
  scanf("%d%d", &N, &M);
  for (i = 1; i <= N; i++) {
    scanf("%d", a + i);
    for (j = 0; j < K; j++) cal[i][j] = (cal[i - 1][j] + power(i, j)) % MOD;
  }
  nCk();
  init(1, 1, N);
  while (M--) {
    scanf("%s%d%d%d", t, &l, &r, &x);
    if (t[0] == '?') {
      vector<long long> ans(6);
      read(1, 1, N, l, r, x, ans);
      cout << ((ans[x] + MOD) % MOD) << endl;
    } else {
      update(1, 1, N, l, r, x);
    }
  }
  return 0;
}