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 offset = 1 << 17, MAXN = 100100, MOD = 1000000007;
int koef[6][MAXN], sum[6][MAXN], c[7][7];
void preprocess() {
  for (int i = 0; i < 6; ++i) {
    for (int j = 1; j < MAXN; ++j) {
      koef[i][j] = 1;
      for (int k = 0; k < i; ++k)
        koef[i][j] = ((long long)koef[i][j] * j) % MOD;
      sum[i][j] = (sum[i][j - 1] + koef[i][j]) % MOD;
    }
  }
  c[0][0] = 1;
  for (int i = 1; i < 6; ++i) {
    c[i][0] = 1;
    for (int j = 1; j < 6; ++j) c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
  }
}
struct node {
  vector<int> sum;
  int prop, f;
};
node data[2 * offset];
struct tournament {
  vector<vector<int> *> V;
  vector<int> Lo;
  int calc(int lo, int hi, int val, int k) {
    return ((long long)sum[k][hi - lo] * val) % MOD;
  }
  vector<int> spoji(int l, const vector<int> &L, const vector<int> &D) {
    vector<int> ret(7, 0);
    for (int i = 0; i < 6; ++i) ret[i] = (L[i] + D[i]) % MOD;
    if (!l) return ret;
    int pot[7] = {1};
    for (int i = 1; i < 6; ++i) pot[i] = ((long long)pot[i - 1] * l) % MOD;
    for (int i = 0; i < 6; ++i)
      for (int j = 1; j <= i; ++j)
        ret[i] =
            (ret[i] +
             (((((long long)D[i - j] * pot[j]) % MOD) * (long long)c[i][j]) %
              MOD)) %
            MOD;
    return ret;
  }
  void propagate(int x, int lo, int hi) {
    if (!data[x].f) return;
    int lc = 2 * x, rc = 2 * x + 1, mid = (lo + hi) / 2;
    for (int i = 0; i < 6; ++i) {
      data[lc].sum[i] = calc(lo, mid, data[x].prop, i);
      data[rc].sum[i] = calc(mid, hi, data[x].prop, i);
    }
    data[lc].prop = data[rc].prop = data[x].prop;
    data[lc].f = data[rc].f = 1;
    data[x].f = 0;
  }
  void set(int x, int lo, int hi, int from, int to, int val) {
    if (from >= hi || to <= lo) return;
    if (lo >= from && hi <= to) {
      for (int i = 0; i < 6; ++i) data[x].sum[i] = calc(lo, hi, val, i);
      data[x].prop = val;
      data[x].f = 1;
      return;
    }
    propagate(x, lo, hi);
    set(2 * x, lo, (lo + hi) / 2, from, to, val);
    set(2 * x + 1, (lo + hi) / 2, hi, from, to, val);
    data[x].sum =
        spoji((hi + lo) / 2 - lo, data[2 * x].sum, data[2 * x + 1].sum);
  }
  void get(int x, int lo, int hi, int from, int to) {
    if (from >= hi || to <= lo) return;
    if (lo >= from && hi <= to) {
      V.push_back(&data[x].sum);
      Lo.push_back(lo);
      return;
    }
    propagate(x, lo, hi);
    get(2 * x, lo, (lo + hi) / 2, from, to);
    get(2 * x + 1, (lo + hi) / 2, hi, from, to);
    int mid = (lo + hi) / 2;
  }
  void build(int x, int lo, int hi) {
    if (x >= offset) return;
    int mid = (lo + hi) / 2;
    build(2 * x, lo, mid);
    build(2 * x + 1, mid, hi);
    data[x].sum = spoji(mid - lo, data[2 * x].sum, data[2 * x + 1].sum);
  }
  void at(int x, int t) {
    for (int i = 0; i < 6; ++i) data[x + offset].sum[i] = t;
  }
  tournament() {
    for (int i = 0; i < 2 * offset; ++i) data[i].sum.resize(7, 0);
  }
  int query(int from, int to, int k) {
    vector<int> rez;
    V.clear();
    Lo.clear();
    rez.clear();
    get(1, 0, offset, from, to);
    rez = *V[0];
    for (int i = 1; i < (int)V.size(); ++i)
      rez = spoji(Lo[i] - from, rez, *V[i]);
    return rez[k];
  }
} T;
int main() {
  char tip;
  int n, m, l, r, k, t;
  preprocess();
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; ++i) {
    scanf("%d", &t);
    T.at(i, t);
  }
  T.build(1, 0, offset);
  for (int i = 0; i < m; ++i) {
    scanf(" %c %d %d %d", &tip, &l, &r, &k);
    if (tip == '=')
      T.set(1, 0, offset, l - 1, r, k);
    else
      printf("%d\n", T.query(l - 1, r, k));
  }
  return 0;
}