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 double Pi = acos(-1.0);
const int inf = 1000000007;
const long long llinf = 800000000000000119;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
template <class T>
ostream& operator<<(ostream& stream, vector<T> v) {
  for (T i : v) {
    stream << i << " ";
  }
  stream << "\b";
  return stream;
}
void hi() { printf("hi\n"); }
template <const int& MOD>
struct _m_int {
  int val;
  _m_int(int64_t v = 0) {
    if (v < 0) v = v % MOD + MOD;
    if (v >= MOD) v %= MOD;
    val = int(v);
  }
  static int inv_mod(int a, int m = MOD) {
    int g = m, r = a, x = 0, y = 1;
    while (r != 0) {
      int q = g / r;
      g %= r;
      swap(g, r);
      x -= q * y;
      swap(x, y);
    }
    return x < 0 ? x + m : x;
  }
  explicit operator int() const { return val; }
  explicit operator int64_t() const { return val; }
  _m_int& operator+=(const _m_int& other) {
    val -= MOD - other.val;
    if (val < 0) val += MOD;
    return *this;
  }
  _m_int& operator-=(const _m_int& other) {
    val -= other.val;
    if (val < 0) val += MOD;
    return *this;
  }
  static unsigned fast_mod(uint64_t x, unsigned m = MOD) {
    return unsigned(x % m);
  }
  _m_int& operator*=(const _m_int& other) {
    val = fast_mod(uint64_t(val) * other.val);
    return *this;
  }
  _m_int& operator/=(const _m_int& other) { return *this *= other.inv(); }
  friend _m_int operator+(const _m_int& a, const _m_int& b) {
    return _m_int(a) += b;
  }
  friend _m_int operator-(const _m_int& a, const _m_int& b) {
    return _m_int(a) -= b;
  }
  friend _m_int operator*(const _m_int& a, const _m_int& b) {
    return _m_int(a) *= b;
  }
  friend _m_int operator/(const _m_int& a, const _m_int& b) {
    return _m_int(a) /= b;
  }
  _m_int& operator++() {
    val = val == MOD - 1 ? 0 : val + 1;
    return *this;
  }
  _m_int& operator--() {
    val = val == 0 ? MOD - 1 : val - 1;
    return *this;
  }
  _m_int operator++(int) {
    _m_int before = *this;
    ++*this;
    return before;
  }
  _m_int operator--(int) {
    _m_int before = *this;
    --*this;
    return before;
  }
  _m_int operator-() const { return val == 0 ? 0 : MOD - val; }
  bool operator==(const _m_int& other) const { return val == other.val; }
  bool operator!=(const _m_int& other) const { return val != other.val; }
  _m_int inv() const { return inv_mod(val); }
  _m_int pow(int64_t p) const {
    if (p < 0) return inv().pow(-p);
    _m_int a = *this, result = 1;
    while (p > 0) {
      if (p & 1) result *= a;
      p >>= 1;
      if (p > 0) a *= a;
    }
    return result;
  }
  friend ostream& operator<<(ostream& os, const _m_int& m) {
    return os << m.val;
  }
};
using mod_int = _m_int<inf>;
mod_int f_exp(mod_int base, long long power) {
  if (power == 0) return 1;
  if (power == 1) return base;
  mod_int ans = f_exp(base, power / 2);
  ans *= ans;
  if (power % 2 == 1) ans *= base;
  return ans;
}
mod_int presum[100010][6];
mod_int sumn(int l, int r, int k) {
  if (l == 0) {
    return presum[r][k];
  }
  return presum[r][k] - presum[l - 1][k];
}
class segment_tree {
 public:
  struct node {
    mod_int sum[6], flag;
  };
  node tree[4 * 100010];
  void update(int n, int nl, int nr, mod_int v) {
    for (int i = 0; i < 6; i++) {
      tree[n].sum[i] = sumn(nl, nr, i) * v;
    }
    tree[n].flag = v;
  }
  void lazy(int n, int nl, int nr) {
    if (tree[n].flag == -1) return;
    int nm = nl + (nr - nl) / 2;
    update(n * 2, nl, nm, tree[n].flag);
    update(n * 2 + 1, nm + 1, nr, tree[n].flag);
    tree[n].flag = -1;
  }
  void merge(int n, int nl, int nr) {
    for (int i = 0; i < 6; i++) {
      tree[n].sum[i] = tree[n * 2].sum[i] + tree[n * 2 + 1].sum[i];
    }
  }
  void update(int n, int nl, int nr, int l, int r, mod_int v) {
    if (l <= nl && nr <= r) {
      update(n, nl, nr, v);
      return;
    }
    lazy(n, nl, nr);
    int nm = nl + (nr - nl) / 2;
    if (l <= nm) update(n * 2, nl, nm, l, r, v);
    if (nm < r) update(n * 2 + 1, nm + 1, nr, l, r, v);
    merge(n, nl, nr);
  }
  mod_int query(int n, int nl, int nr, int l, int r, int k) {
    if (l <= nl && nr <= r) {
      return tree[n].sum[k];
    }
    lazy(n, nl, nr);
    int nm = nl + (nr - nl) / 2;
    mod_int sum = 0;
    if (l <= nm) sum += query(n * 2, nl, nm, l, r, k);
    if (nm < r) sum += query(n * 2 + 1, nm + 1, nr, l, r, k);
    return sum;
  }
} segtree;
int n, m;
mod_int ncr[6][6] = {{1},          {1, 1},          {1, 2, 1},
                     {1, 3, 3, 1}, {1, 4, 6, 4, 1}, {1, 5, 10, 10, 5, 1}};
mod_int get_s(int l, int r, int k) {
  mod_int res = 0;
  for (int i = 0; i <= k; i++) {
    res += segtree.query(1, 0, n - 1, l, r, i) * f_exp(-l, k - i) * ncr[k][i];
  }
  return res;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  for (int i = 0; i < 6; i++) {
    presum[0][i] = 1;
  }
  for (int i = 1; i < n; i++) {
    for (int j = 0; j < 6; j++) {
      presum[i][j] = presum[i - 1][j] + f_exp(i + 1, j);
    }
  }
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    segtree.update(1, 0, n - 1, i, i, x);
  }
  for (int i = 0; i < m; i++) {
    char type;
    cin >> type;
    int l, r, x;
    cin >> l >> r >> x;
    l--;
    r--;
    if (type == '=') {
      segtree.update(1, 0, n - 1, l, r, x);
    } else {
      cout << get_s(l, r, x) << endl;
    }
  }
  return 0;
}