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 long long N = 1e5 + 5, mod = 1e9 + 7;
long long pw[6][N], lazy[6][4 * N], t[6][4 * N];
inline long long mull(long long a, long long b) { return (a * b) % mod; }
long long power(long long x, long long y, long long p) {
  long long res = 1;
  x = x % p;
  while (y > 0) {
    if (y & 1) res = (res * x) % p;
    y = y >> 1;
    x = (x * x) % p;
  }
  return res;
}
long long modInverse(long long n, long long p) { return power(n, p - 2, p); }
inline long long add(long long a, long long b) { return (a + b) % mod; }
void push(long long id, long long l, long long r) {
  for (long long i = 0; i < 6; i++) {
    if (lazy[i][id] == -1) continue;
    t[i][id] = mull(lazy[i][id], (pw[i][r] - pw[i][l - 1] + mod) % mod);
    if (l != r) {
      lazy[i][id << 1] = lazy[i][id];
      lazy[i][id << 1 | 1] = lazy[i][id];
    }
    lazy[i][id] = -1;
  }
}
void update(long long id, long long lq, long long rq, long long l, long long r,
            long long val) {
  push(id, l, r);
  if (l > r || lq > r || l > rq) return;
  if (lq <= l and rq >= r) {
    for (long long i = 0; i < 6; i++) lazy[i][id] = val;
    push(id, l, r);
    return;
  }
  long long mid = (l + r) >> 1;
  update(id << 1, lq, rq, l, mid, val);
  update(id << 1 | 1, lq, rq, mid + 1, r, val);
  for (long long i = 0; i < 6; i++)
    t[i][id] = add(t[i][id << 1], t[i][id << 1 | 1]);
}
long long get(long long id, long long l, long long r, long long lq,
              long long rq, long long k) {
  push(id, l, r);
  if (l > r || lq > r || l > rq) return 0;
  if (lq <= l and rq >= r) {
    return t[k][id];
  }
  long long mid = (l + r) >> 1;
  return (get(id << 1, l, mid, lq, rq, k) +
          get(id << 1 | 1, mid + 1, r, lq, rq, k)) %
         mod;
}
void pre() {
  memset(pw, 0, sizeof(pw));
  memset(lazy, -1, sizeof(lazy));
  memset(t, 0, sizeof(t));
  for (long long i = 0; i <= 5; i++) {
    for (long long j = 1; j < N; j++) {
      pw[i][j] = power(j, i, mod);
    }
  }
  for (long long i = 0; i <= 5; i++) {
    for (long long j = 1; j < N; j++) {
      pw[i][j] = add(pw[i][j], pw[i][j - 1]);
    }
  }
}
inline long long sub(long long a, long long b) { return (a - b + mod) % mod; }
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  pre();
  long long n, m;
  cin >> n >> m;
  long long a[n];
  for (long long i = 0; i < n; i++) cin >> a[i];
  for (long long i = 0; i < n; i++) update(1, i + 1, i + 1, 1, n, a[i]);
  while (m--) {
    char c;
    cin >> c;
    long long l, r, x;
    cin >> l >> r >> x;
    if (c == '=')
      update(1, l, r, 1, n, x);
    else {
      long long ans = get(1, 1, n, l, r, x);
      if (x == 0)
        cout << ans % mod << "\n";
      else if (x == 1) {
        ans = sub(ans, mull(l - 1, get(1, 1, n, l, r, 0)));
        cout << ans << "\n";
      } else if (x == 2) {
        ans = add(ans, mull(power(l - 1, 2, mod), get(1, 1, n, l, r, 0)));
        long long tmp;
        tmp = mull(2, l - 1);
        tmp = mull(tmp, get(1, 1, n, l, r, 1));
        ans = sub(ans, tmp);
        cout << ans << "\n";
      } else if (x == 3) {
        ans = sub(ans, mull(power(l - 1, 3, mod), get(1, 1, n, l, r, 0)));
        long long tmp = mull(3, mull(l - 1, get(1, 1, n, l, r, 2)));
        ans = sub(ans, tmp);
        tmp = mull(3, mull(power(l - 1, 2, mod), get(1, 1, n, l, r, 1)));
        ans = add(ans, tmp);
        cout << ans << "\n";
      } else if (x == 4) {
        ans = sub(ans, mull(4, mull(l - 1, get(1, 1, n, l, r, 3))));
        ans = add(ans,
                  mull(6, mull(power(l - 1, 2, mod), get(1, 1, n, l, r, 2))));
        ans = sub(ans,
                  mull(4, mull(power(l - 1, 3, mod), get(1, 1, n, l, r, 1))));
        ans = add(ans, mull(power(l - 1, 4, mod), get(1, 1, n, l, r, 0)));
        cout << ans << "\n";
      } else {
        ans = sub(ans, mull(5, mull(l - 1, get(1, 1, n, l, r, 4))));
        ans = add(ans,
                  mull(10, mull(power(l - 1, 2, mod), get(1, 1, n, l, r, 3))));
        ans = sub(ans,
                  mull(10, mull(power(l - 1, 3, mod), get(1, 1, n, l, r, 2))));
        ans = add(ans,
                  mull(5, mull(power(l - 1, 4, mod), get(1, 1, n, l, r, 1))));
        ans = sub(ans, mull(power(l - 1, 5, mod), get(1, 1, n, l, r, 0)));
        cout << ans << "\n";
      }
    }
  }
  return 0;
}