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>
constexpr long long mod = 1000000007;
inline long long read() noexcept {
  char c;
  while (!isdigit(c = getchar()))
    ;
  long long ans = static_cast<long long>(c) - '0';
  while (isdigit(c = getchar())) {
    ans = (ans << 3) + (ans << 1) + (static_cast<long long>(c) - '0');
  }
  return ans;
}
long long _power_sum[100001][6], power[100001][6];
inline long long power_sum(const long long& l, const long long& r,
                           const long long& n) noexcept {
  return (_power_sum[r][n] - _power_sum[l - 1][n] + mod) % mod;
}
class SegTree {
 public:
  struct data_struct {
    long long val[6];
    inline const long long operator[](const long long& pos) const noexcept {
      return val[pos];
    }
    inline long long& operator[](const long long& pos) noexcept {
      return val[pos];
    }
    data_struct() noexcept : val() {
      for (long long i = 0; i < 6; ++i) {
        val[i] = 0;
      }
    }
  };

 private:
  bool use_tag;
  long long l, r, tag;
  data_struct data;
  SegTree *lc, *rc;
  inline void maintain() noexcept {
    if (l < r) {
      if (use_tag) {
        for (long long i = 0; i <= 5; ++i) {
          data[i] = tag * power_sum(l, r, i) % mod;
        }
      } else {
        for (long long i = 0; i <= 5; ++i) {
          data[i] = (lc->data[i] + rc->data[i]) % mod;
        }
      }
    }
    return;
  }
  inline void add_tag(const long long& val) noexcept {
    use_tag = 1;
    tag = val;
    for (long long i = 0; i <= 5; ++i) {
      data[i] = tag * power_sum(l, r, i) % mod;
    }
    return;
  }
  inline void down_tag() noexcept {
    if (use_tag) {
      if (l < r) {
        lc->add_tag(tag);
        rc->add_tag(tag);
      }
      use_tag = 0;
    }
    return;
  }

 public:
  SegTree(const long long& _l, const long long& _r) noexcept
      : l(_l), r(_r), data(), lc(nullptr), rc(nullptr), use_tag(0), tag() {
    const long long mid = (l + r) >> 1;
    if (l == r) {
      data[0] = read() % mod;
      for (long long i = 1; i <= 5; ++i) {
        data[i] = data[i - 1] * mid % mod;
      }
    } else {
      lc = new SegTree(l, mid);
      rc = new SegTree(mid + 1, r);
      maintain();
    }
  }
  ~SegTree() noexcept {
    delete lc;
    delete rc;
  }
  inline void change(const long long& L, const long long& R,
                     const long long& val) noexcept {
    if (l == L && R == r) {
      add_tag(val);
    } else {
      down_tag();
      if (R <= lc->r) {
        lc->change(L, R, val);
      } else if (rc->l <= L) {
        rc->change(L, R, val);
      } else {
        lc->change(L, lc->r, val);
        rc->change(rc->l, R, val);
      }
      maintain();
    }
    return;
  }
  inline data_struct query(long long L, long long R) noexcept {
    if (l == L && R == r) {
      return data;
    }
    down_tag();
    if (R <= lc->r) {
      return lc->query(L, R);
    }
    if (rc->l <= L) {
      return rc->query(L, R);
    }
    auto ans = lc->query(L, lc->r);
    const auto t = rc->query(rc->l, R);
    for (long long i = 0; i <= 5; ++i) {
      ans[i] += t[i];
      ans[i] %= mod;
    }
    return ans;
  }
};
int main() noexcept {
  const long long n = read(), m = read();
  for (long long i = 0; i <= n; ++i) {
    power[i][0] = 1;
    for (long long j = 1; j <= 5; ++j) {
      power[i][j] = power[i][j - 1] * i % mod;
    }
  }
  for (long long i = 0; i <= 5; ++i) {
    _power_sum[0][i] = 0;
    for (long long j = 1; j <= n; ++j) {
      _power_sum[j][i] = (_power_sum[j - 1][i] + power[j][i]) % mod;
    }
  }
  SegTree* tr = new SegTree(1, n);
  for (long long i = 1; i <= m; ++i) {
    char com;
    while ((com = getchar()) != '=' && com != '?')
      ;
    if (com == '=') {
      const long long l = read(), r = read(), val = read();
      tr->change(l, r, val);
    } else {
      const long long lM1 = read() - 1;
      const auto data = tr->query(lM1 + 1, read());
      const long long times = read();
      long long ans = 0;
      switch (times) {
        case 0:
          ans += data[0];
          break;
        case 1:
          ans += data[1];
          ans -= power[lM1][1] * data[0] % mod;
          ans = (ans + mod) % mod;
          break;
        case 2:
          ans += data[2];
          ans -= 2 * power[lM1][1] % mod * data[1] % mod;
          ans = (ans + mod) % mod;
          ans += power[lM1][2] * data[0] % mod;
          ans %= mod;
          break;
        case 3:
          ans += data[3];
          ans -= 3 * power[lM1][1] % mod * data[2] % mod;
          ans = (ans + mod) % mod;
          ans += 3 * power[lM1][2] % mod * data[1] % mod;
          ans %= mod;
          ans -= power[lM1][3] * data[0] % mod;
          ans = (ans + mod) % mod;
          break;
        case 4:
          ans += data[4];
          ans -= 4 * power[lM1][1] % mod * data[3] % mod;
          ans = (ans + mod) % mod;
          ans += 6 * power[lM1][2] % mod * data[2] % mod;
          ans %= mod;
          ans -= 4 * power[lM1][3] % mod * data[1] % mod;
          ans = (ans + mod) % mod;
          ans += power[lM1][4] * data[0] % mod;
          ans %= mod;
          break;
        case 5:
          ans += data[5];
          ans -= 5 * power[lM1][1] % mod * data[4] % mod;
          ans = (ans + mod) % mod;
          ans += 10 * power[lM1][2] % mod * data[3] % mod;
          ans %= mod;
          ans -= 10 * power[lM1][3] % mod * data[2] % mod;
          ans = (ans + mod) % mod;
          ans += 5 * power[lM1][4] % mod * data[1] % mod;
          ans %= mod;
          ans -= power[lM1][5] * data[0] % mod;
          ans = (ans + mod) % mod;
          break;
      }
      printf("%lld\n", ans);
    }
  }
  delete tr;
  return 0;
}