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>
#pragma GCC optimize("O3")
using namespace std;
int add(int a, int b) {
  long long x = a + b;
  if (x >= 1000000007) x -= 1000000007;
  if (x < 0) x += 1000000007;
  return x;
}
long long mul(long long a, long long b) { return (a * b) % 1000000007; }
long long pw(long long a, long long b) {
  long long ans = 1;
  while (b) {
    if (b & 1) ans = (ans * a) % 1000000007;
    a = (a * a) % 1000000007;
    b >>= 1;
  }
  return ans;
}
int n, m, x, L, R;
long long pre[100005][6];
long long sum[400005][6];
int laz[400005];
inline void pushdown(int rt, int l, int r) {
  if (laz[rt] != -1) {
    int m = (l + r) >> 1;
    for (int i = 0; i <= 5; ++i) {
      sum[rt << 1][i] =
          ((pre[m][i] - pre[l - 1][i]) % 1000000007 + 1000000007) % 1000000007 *
          laz[rt] % 1000000007;
      sum[rt << 1 | 1][i] =
          ((pre[r][i] - pre[m][i]) % 1000000007 + 1000000007) % 1000000007 *
          laz[rt] % 1000000007;
    }
    laz[rt << 1] = laz[rt << 1 | 1] = laz[rt];
    laz[rt] = -1;
  }
}
void build(int rt, int l, int r) {
  laz[rt] = -1;
  if (l == r) {
    cin >> x;
    sum[rt][0] = x;
    for (int i = 1; i <= 5; ++i) sum[rt][i] = sum[rt][i - 1] * l % 1000000007;
    return;
  }
  int m = (l + r) / 2;
  build(rt << 1, l, m);
  build(rt << 1 | 1, m + 1, r);
  for (int i = 0; i <= 5; ++i)
    sum[rt][i] = add(sum[rt << 1][i], sum[rt << 1 | 1][i]);
}
void setv(int rt, int l, int r) {
  if (L <= l && r <= R) {
    laz[rt] = x;
    for (int i = 0; i <= 5; ++i)
      sum[rt][i] = ((pre[r][i] - pre[l - 1][i]) % 1000000007 + 1000000007) %
                   1000000007 * x % 1000000007;
    return;
  }
  pushdown(rt, l, r);
  int m = (l + r) / 2;
  if (L <= m) setv(rt << 1, l, m);
  if (R > m) setv(rt << 1 | 1, m + 1, r);
  for (int i = 0; i <= 5; ++i)
    sum[rt][i] = add(sum[rt << 1][i], sum[rt << 1 | 1][i]);
}
long long query(int d, int rt, int l, int r) {
  if (L <= l && r <= R) return sum[rt][d];
  pushdown(rt, l, r);
  int m = (l + r) >> 1;
  long long ret = 0;
  if (L <= m) ret += query(d, rt << 1, l, m);
  if (R > m) ret += query(d, rt << 1 | 1, m + 1, r);
  ret %= 1000000007;
  for (int i = 0; i <= 5; ++i)
    sum[rt][i] = add(sum[rt << 1][i], sum[rt << 1 | 1][i]);
  return ret;
}
long long solve() {
  long long ret;
  long long u = L - 1;
  if (x == 0) ret = query(0, 1, 1, n);
  if (x == 1) {
    ret = query(1, 1, 1, n) - u * query(0, 1, 1, n) % 1000000007;
    ret = (ret % 1000000007 + 1000000007) % 1000000007;
    return ret;
  }
  if (x == 2) {
    ret = query(2, 1, 1, n) - 2ll * u * query(1, 1, 1, n) % 1000000007;
    ret = (ret % 1000000007 + 1000000007) % 1000000007;
    ret = ret + (long long)u * u % 1000000007 * query(0, 1, 1, n) % 1000000007;
    ret = (ret % 1000000007 + 1000000007) % 1000000007;
  }
  if (x == 3) {
    ret = query(3, 1, 1, n) - 3ll * u * query(2, 1, 1, n) % 1000000007;
    ret = (ret % 1000000007 + 1000000007) % 1000000007;
    ret = ret + 3ll * u * u % 1000000007 * query(1, 1, 1, n) % 1000000007;
    ret = (ret % 1000000007 + 1000000007) % 1000000007;
    ret = ret -
          u * u % 1000000007 * u % 1000000007 * query(0, 1, 1, n) % 1000000007;
    ret = (ret % 1000000007 + 1000000007) % 1000000007;
  }
  if (x == 4) {
    ret = query(4, 1, 1, n) - 4ll * u * query(3, 1, 1, n) % 1000000007;
    ret = (ret % 1000000007 + 1000000007) % 1000000007;
    ret = ret + 6ll * u * u % 1000000007 * query(2, 1, 1, n) % 1000000007;
    ret = (ret % 1000000007 + 1000000007) % 1000000007;
    ret = ret - 4ll * u * u % 1000000007 * u % 1000000007 * query(1, 1, 1, n) %
                    1000000007;
    ret = (ret % 1000000007 + 1000000007) % 1000000007;
    ret = ret + u * u % 1000000007 * u % 1000000007 * u % 1000000007 *
                    query(0, 1, 1, n) % 1000000007;
    ret = (ret % 1000000007 + 1000000007) % 1000000007;
  }
  if (x == 5) {
    ret = query(5, 1, 1, n) - 5ll * u * query(4, 1, 1, n) % 1000000007;
    ret = (ret % 1000000007 + 1000000007) % 1000000007;
    ret = ret + 10ll * u * u % 1000000007 * query(3, 1, 1, n) % 1000000007;
    ret = (ret % 1000000007 + 1000000007) % 1000000007;
    ret = ret - 10ll * u * u % 1000000007 * u % 1000000007 * query(2, 1, 1, n) %
                    1000000007;
    ret = (ret % 1000000007 + 1000000007) % 1000000007;
    ret = ret + 5ll * u * u % 1000000007 * u % 1000000007 * u % 1000000007 *
                    query(1, 1, 1, n) % 1000000007;
    ret = (ret % 1000000007 + 1000000007) % 1000000007;
    ret = ret - u * u % 1000000007 * u % 1000000007 * u % 1000000007 * u %
                    1000000007 * query(0, 1, 1, n) % 1000000007;
    ret = (ret % 1000000007 + 1000000007) % 1000000007;
  }
  return ret;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    long long t = 1;
    for (int j = 0; j <= 5; ++j) {
      pre[i][j] = add(pre[i - 1][j], t);
      t = mul(t, i);
    }
  }
  build(1, 1, n);
  char s;
  for (int i = 1; i <= m; ++i) {
    cin >> s >> L >> R >> x;
    if (s == '=')
      setv(1, 1, n);
    else
      cout << solve() << '\n';
  }
  return 0;
}