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 + 9, mod = 1e9 + 7;
template <int32_t MOD>
struct modint {
  int32_t value;
  modint() = default;
  modint(int32_t value_) : value(value_) {}
  inline modint<MOD> operator+(modint<MOD> other) const {
    int32_t c = this->value + other.value;
    return modint<MOD>(c >= MOD ? c - MOD : c);
  }
  inline modint<MOD> operator-(modint<MOD> other) const {
    int32_t c = this->value - other.value;
    return modint<MOD>(c < 0 ? c + MOD : c);
  }
  inline modint<MOD> operator*(modint<MOD> other) const {
    int32_t c = (int64_t)this->value * other.value % MOD;
    return modint<MOD>(c < 0 ? c + MOD : c);
  }
  inline modint<MOD>& operator+=(modint<MOD> other) {
    this->value += other.value;
    if (this->value >= MOD) this->value -= MOD;
    return *this;
  }
  inline modint<MOD>& operator-=(modint<MOD> other) {
    this->value -= other.value;
    if (this->value < 0) this->value += MOD;
    return *this;
  }
  inline modint<MOD>& operator*=(modint<MOD> other) {
    this->value = (int64_t)this->value * other.value % MOD;
    if (this->value < 0) this->value += MOD;
    return *this;
  }
  inline modint<MOD> operator-() const {
    return modint<MOD>(this->value ? MOD - this->value : 0);
  }
  modint<MOD> pow(uint64_t k) const {
    modint<MOD> x = *this, y = 1;
    for (; k; k >>= 1) {
      if (k & 1) y *= x;
      x *= x;
    }
    return y;
  }
  modint<MOD> inv() const { return pow(MOD - 2); }
  inline modint<MOD> operator/(modint<MOD> other) const {
    return *this * other.inv();
  }
  inline modint<MOD> operator/=(modint<MOD> other) {
    return *this *= other.inv();
  }
  inline bool operator==(modint<MOD> other) const {
    return value == other.value;
  }
  inline bool operator!=(modint<MOD> other) const {
    return value != other.value;
  }
};
template <int32_t MOD>
modint<MOD> operator*(int64_t value, modint<MOD> n) {
  return modint<MOD>(value) * n;
}
template <int32_t MOD>
modint<MOD> operator*(int32_t value, modint<MOD> n) {
  return modint<MOD>(value % MOD) * n;
}
template <int32_t MOD>
ostream& operator<<(ostream& out, modint<MOD> n) {
  return out << n.value;
}
using mint = modint<mod>;
mint C[6][6], pw[6][N];
template <typename T>
struct segtree {
  vector<T> t[6];
  vector<int> lazy, a;
  int x;
  segtree() {}
  segtree(int n) {
    x = n;
    for (int i = 0; i <= 5; i++) t[i].assign(4 * n, mint(0));
    lazy.assign(4 * n, -1);
    a.assign(n + 1, 0);
  }
  void push(int n, int b, int e) {
    if (lazy[n] == -1) return;
    for (int k = 0; k <= 5; k++) t[k][n] = (pw[k][e] - pw[k][b - 1]) * lazy[n];
    if (b != e) {
      lazy[(n << 1)] = lazy[n];
      lazy[((n << 1) | 1)] = lazy[n];
    }
    lazy[n] = -1;
  }
  void pull(int n) {
    for (int k = 0; k <= 5; k++)
      t[k][n] = t[k][(n << 1)] + t[k][((n << 1) | 1)];
  }
  void build(int n, int b, int e) {
    if (b > e) return;
    if (b == e) {
      for (int k = 0; k <= 5; k++)
        t[k][n] = (pw[k][b] - pw[k][b - 1]) * a[b - 1];
      return;
    }
    int mid = (b + e) >> 1;
    build((n << 1), b, mid);
    build(((n << 1) | 1), mid + 1, e);
    pull(n);
  }
  void upd(int n, int b, int e, int i, int j, int v) {
    push(n, b, e);
    if (j < b || e < i) return;
    if (i <= b && e <= j) {
      lazy[n] = v;
      push(n, b, e);
      return;
    }
    int mid = (b + e) >> 1;
    upd((n << 1), b, mid, i, j, v);
    upd(((n << 1) | 1), mid + 1, e, i, j, v);
    pull(n);
  }
  mint sum[6];
  void query(int n, int b, int e, int i, int j) {
    push(n, b, e);
    if (i > e || b > j) return;
    if (i <= b && e <= j) {
      for (int k = 0; k <= 5; k++) sum[k] += t[k][n];
      return;
    }
    int mid = (b + e) >> 1;
    query((n << 1), b, mid, i, j);
    query(((n << 1) | 1), mid + 1, e, i, j);
  }
  void build(vector<int>& v) {
    a = v;
    build(1, 1, x);
  }
  void upd(int i, int j, int v) { upd(1, 1, x, i, j, v); }
  T query(int i, int j, int k) {
    for (int k = 0; k < 6; k++) sum[k] = 0;
    query(1, 1, x, i, j);
    mint y = mint(1) - i;
    mint ans = 0;
    for (int j = 0; j <= k; j++) {
      ans += C[k][j] * (y.pow(j)) * sum[k - j];
    }
    return ans;
  }
};
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  for (int i = 0; i < 6; i++) C[i][0] = 1;
  for (int i = 1; i < 6; i++)
    for (int j = 1; j < 6; j++) C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
  for (int k = 0; k <= 5; k++) {
    for (int i = 0; i < N; i++) {
      pw[k][i] = mint(i).pow(k);
      if (i) pw[k][i] += pw[k][i - 1];
    }
  }
  int n, q;
  cin >> n >> q;
  vector<int> a(n);
  for (int i = 0; i < n; i++) cin >> a[i];
  segtree<mint> t(n);
  t.build(a);
  while (q--) {
    char ch;
    int l, r, k;
    cin >> ch >> l >> r >> k;
    if (ch == '=') {
      t.upd(l, r, k);
    } else
      cout << t.query(l, r, k) << '\n';
  }
  return 0;
}