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 MaxN = 100001, MaxK = 6;
long long int preSum[MaxN][MaxK], mod = 1000000007;
struct ST {
  vector<long long int> T, L;
  int N, P;
  void in(vector<int> &t, int x, int y, int n) {
    L[n] = -1;
    if (x + 1 == y) {
      T[n] = t[x];
      return;
    }
    in(t, x, (x + y) / 2, 2 * n);
    in(t, (x + y) / 2, y, 2 * n + 1);
    T[n] = (T[2 * n] + T[2 * n + 1]) % mod;
  }
  void init(vector<int> &t, int p) {
    N = t.size(), P = p;
    T.resize(4 * N);
    L.resize(4 * N);
    in(t, 0, N, 1);
  }
  void push(int x, int y, int n) {
    if (L[n] != -1) {
      T[n] = (preSum[y][P] - preSum[x][P] + mod) % mod;
      T[n] = (T[n] * L[n]) % mod;
      if (x + 1 != y) L[2 * n] = L[2 * n + 1] = L[n];
      L[n] = -1;
    }
  }
  long long int qry(int x, int y, int n, int &l, int &r) {
    push(x, y, n);
    if (l <= x && y <= r) return T[n];
    if (y <= l || r <= x) return 0;
    long long int I, D;
    I = qry(x, (x + y) / 2, 2 * n, l, r);
    D = qry((x + y) / 2, y, 2 * n + 1, l, r);
    T[n] = (T[2 * n] + T[2 * n + 1]) % mod;
    return (I + D) % mod;
  }
  long long int query(int x, int y) {
    x--;
    return qry(0, N, 1, x, y);
  }
  void upd(int x, int y, int n, int &l, int &r, int &v) {
    push(x, y, n);
    if (l <= x && y <= r) {
      L[n] = v;
      push(x, y, n);
      return;
    }
    if (y <= l || r <= x) return;
    upd(x, (x + y) / 2, 2 * n, l, r, v);
    upd((x + y) / 2, y, 2 * n + 1, l, r, v);
    T[n] = (T[2 * n] + T[2 * n + 1]) % mod;
  }
  void update(int x, int y, int v) {
    x--;
    upd(0, N, 1, x, y, v);
  }
  void dfs(int x, int y, int n) {
    push(x, y, n);
    if (x + 1 == y) {
      cout << T[n] << " ";
      return;
    }
    dfs(x, (x + y) / 2, n * 2);
    dfs((x + y) / 2, y, 2 * n + 1);
  }
};
ST power[MaxK];
int arr[MaxN], combi[MaxK][MaxK], N;
long long int query(int x, int y, int k) {
  long long int pot = 1, i, ans = 0;
  for (i = k; i >= 0; i--, pot = (pot * ((1 - x + mod) % mod)) % mod) {
    ans = (ans + (power[i].query(x, y) * ((combi[k][i] * pot) % mod)) % mod) %
          mod;
  }
  return ans;
}
void update(int x, int y, int v) {
  for (int i = 0; i < MaxK; i++) {
    power[i].update(x, y, v);
  }
}
int main() {
  cin.tie(0), ios_base::sync_with_stdio(0);
  int i, j, p, q, M, r, x, y, v;
  char op;
  cin >> N >> M;
  for (i = 1; i <= N; i++) cin >> arr[i];
  vector<int> t(N);
  for (i = 1; i <= N; i++) {
    preSum[i][0] = 1;
    t[i - 1] = arr[i];
  }
  power[0].init(t, 0);
  for (j = 1; j < MaxK; j++) {
    for (i = 1; i <= N; i++) {
      preSum[i][j] = (i * preSum[i][j - 1]) % mod;
      t[i - 1] = (arr[i] * preSum[i][j]) % mod;
    }
    power[j].init(t, j);
  }
  for (i = 1; i <= N; i++)
    for (j = 0; j < MaxK; j++)
      preSum[i][j] = (preSum[i][j] + preSum[i - 1][j]) % mod;
  for (i = 0; i < MaxK; i++) combi[i][i] = combi[i][0] = 1;
  for (i = 1; i < MaxK; i++)
    for (j = 1; j < i; j++)
      combi[i][j] = (combi[i - 1][j] + combi[i - 1][j - 1]) % mod;
  for (i = 0; i < M; i++) {
    cin >> op >> x >> y >> v;
    if (op == '=') update(x, y, v);
    if (op == '?') cout << query(x, y, v) << "\n";
  }
}